Reverse Vowels of a String - LeetCode

https://leetcode.com/problems/reverse-vowels-of-a-string/?envType=study-plan-v2&envId=leetcode-75

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"

Example 2:

Input: s = "leetcode"
Output: "leotcede"

Constraints:

1 <= s.length <= 3 * 105
s consist of printable ASCII characters.

首先还是审题问题，reverse的含义是翻转，第一次就理解错了，这显然得不到正确的答案，翻转应该是分别从前和后找元音字母，交换位置。这样就简单多了。

思路就是一个从前往后，一个从后往前，接着交换，等满足截止条件后，停止。

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowel_char = "aeiouAEIOU"
        vowels = str(vowel_char)
        s_list = list(s)
        left, right = 0, len(s) - 1

        while left < right:
            while s_list[left] not in vowels and left != right:
                left += 1

            while s_list[right] not in vowels and left != right:
                right -= 1

            temp = s_list[left]
            s_list[left] = s_list[right]
            s_list[right] = temp
            left += 1
            right -= 1

        return ''.join(s_list)

python中没有指针的概念，可以用两个标记来代替。

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = 'aeiouAEIOU'
        stack = [c for c in s if c in vowels]
        
        res = []
        for c in s:
            if c in vowels:
                res.append(stack.pop())
            else:
                res.append(c)
        return ''.join(res)

class Solution {
    public String reverseVowels(String s) {
        String vowels = "aeiouAEIOU";

        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()){
            if (vowels.contains(String.valueOf(c))){
                stack.push(c);
            }
        }

        StringBuilder result = new StringBuilder();
        for (char c : s.toCharArray()){
            if (vowels.contains(String.valueOf(c))){
                result.append(stack.pop());
            }
            else {
                result.append(c);
            }
        }
        return result.toString(); 
    }
}

class Solution {
    public String reverseVowels(String s) {
        int left = 0;
        int right = s.length() - 1;
        String vowels = "aeiouAEIOU";
        char[] charArray = s.toCharArray();

        while(left < right){
            while (left < right && !vowels.contains(String.valueOf(charArray[left]))){
                left ++;
            }
            while (left < right && !vowels.contains(String.valueOf(charArray[right]))){
                right --;
            }
            char temp = charArray[left];
            charArray[left] = charArray[right];
            charArray[right] = temp;
            left ++;
            right --;
        }
        return new String(charArray); 
    }
}

class Solution {
public:
    string reverseVowels(string s) {
        string vowels = "aeiouAEIOU";
        int left = 0;
        int right = s.size() - 1;

        while (left < right) {
            while (left < right && vowels.find(s[left]) == string::npos) {
                left++;
            }
            while (left < right && vowels.find(s[right]) == string::npos) {
                right--;
            }
            std::swap(s[left], s[right]);
            left++;
            right--;
        }

        return s;
    }
};

class Solution {
public:
    string reverseVowels(string s) {
        string vowels = "aeiouAEIOU";

        std::vector<char> stack;
        for (char c : s) {
            if (vowels.find(c) != string::npos){
                stack.push_back(c);
            }
        }

        string result = "";
        for (char c : s){
            if (vowels.find(c) != string::npos){
                result += stack.back();
                stack.pop_back();
            }
            else{
                result += c;
            }
        }
        return result;
    }
};

两种解法：

Using Stack:

Concept:

Every vowel encountered is pushed onto a stack.
When building the reversed string, pop a vowel from the stack each time we encounter a vowel in the original string.

Steps:

Initialize a stack (or a vector as a makeshift stack).
Traverse the string, and for each character, check if it’s a vowel:
- If it’s a vowel, push it onto the stack.
Build the result string:
- Traverse the string again.
- For each character, if it’s a vowel, append the top of the stack to the result and pop the stack.
- If it’s not a vowel, append the character directly to the result.

2. Using Two Pointers:

Concept:

Use two pointers, one starting at the beginning and the other at the end.
Swap the vowels encountered at both pointers.

Steps:

Initialize two pointers, left and right, where left starts at the beginning of the string and right starts at the end.
Traverse the string with the following conditions:
- If the character at left is not a vowel, increment left.
- If the character at right is not a vowel, decrement right.
- If both characters at left and right are vowels, swap them. Then increment left and decrement right.
Continue until left is less than right.

Both methods ensure that only vowels are reversed while the relative positions of consonants remain unchanged. The stack approach might seem more intuitive to some since it captures the idea of reversing by using a data structure designed for LIFO (Last In, First Out) operations. On the other hand, the two pointers method is more space-efficient as it performs the swap in place and doesn’t require any additional data structures. The choice between the two methods depends on one’s familiarity with the concepts and the specific constraints of a given situation.