[LeetCode] 345. Reverse Vowels of a String

1. Question

Given a string s, reverse only all the vowels in the string and return it.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

Example 1:

Input: s = "hello"
Output: "holle"

2. Thoughts

1. have one pointer iterate from start, another from back
2. iterate each pointer untill they are at a vowel
3. change the value of those pointers
4. do so untill the latter pointer is at the same or front than the former pointer

3. Tips learned

3.1 In Python, strings are immutable, so you can't change their characters in-place.

Thus, you cannot do

str1 = "mystring"
str1[5] = u

Else, you need to :

str1 = "mystring"
list1 = list(str1)
list1[5] = 'u'
str1 = ''.join(list1)

4. My solution

class Solution:
    def reverseVowels(self, s: str) -> str:
        string_list = list(s)
        i = 0
        j = len(string_list) - 1
        vowel = ["a", "e", "i", "o", "u", "A", "E", "I", "O", "U"]

        while True:
            while i <= j and string_list[i] not in vowel:
                i += 1
            while i <= j and string_list[j] not in vowel:
                j -= 1

            if i >= j:
                break

            string_list[i], string_list[j] = string_list[j], string_list[i]
            i += 1
            j -= 1
        return "".join(string_list)

5. AI Solution and Improvements

5.1. Refactoring the given code:

There are some issues and redundant checks in your code. Here's a more Pythonic version with comments explaining the changes:

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # Order strings by length
        shorter, longer = sorted([str1, str2], key=len)

        # Check for common prefix which divides both strings
        for i in range(len(shorter), 0, -1):  # Starting from the full length of shorter string and decreasing
            if shorter[:i] * (len(str1) // i) == str1 and shorter[:i] * (len(str2) // i) == str2:
                return shorter[:i]
                
        return ""

The code above directly checks for common prefixes that divide both strings, from the longest possible prefix to the shortest.

5.2. Better solution:

Your solution uses a two-pointer approach, which is a good strategy for this problem. Here are some suggestions to make it more Pythonic:

1. Convert the vowel list to a set. Checking if it is in a set is O(1) on average, while checking if it is in a list is O(n). This will slightly improve the performance.
2. The while True loop can be replaced with while i < j for clearness

Here's a refactored version of your code:

def reverseVowels(s: str) -> str:
    string_list = list(s)
    i, j = 0, len(string_list) - 1
    vowels = set("aeiouAEIOU")

    while i < j:
        while i < j and string_list[i] not in vowels:
            i += 1
        while i < j and string_list[j] not in vowels:
            j -= 1

        string_list[i], string_list[j] = string_list[j], string_list[i]
        i += 1
        j -= 1

    return "".join(string_list)