345. Reverse Vowels of a String

[songyy5517]

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"

Intuition The goal of this problem is to reverse all the vowels in a given string. To achieve reversing, a strightforward idea is to use Double Pointer. One starts from the beginning, the other one from the end of the string, and they move towards each other and stop until they encounter a vowel. Swap the characters at these two pointers, and continue the above procedures until two pointer cross.

[songyy5517]

Approach: Double pointers

1. Exception Handling, and then convert the string to a char array;
2. Define relevant variables:
   • Two pointer left and right pointing at the start and the end of the string;
   • A constant string vowels to store all the vowels.
3. When two pointer have not crossed, do the fowlloing process: （1）Move left backwards until it encounters a vowel; （2）Move right forward until it encounters a vowel; （3）Swap the characters at the two pointers.
4. Return the swapped string.

Complexity Analysis

• Time complexity: $O(N)$ , two pointers travarse through the string which costs the time of $O(N)$ ;
• Space complexity: $O(N)$ , addtionally define a char array of $O(N)$ to store the string to achieve swapping.

[songyy5517]

class Solution {
    public String reverseVowels(String s) {
        // Intuition: Double pointer, Travarase of String.
        // 1. Exception handling
        if (s == null || s.length() == 0)
            return "";

        // 2. Define double pointers.
        char[] str = s.toCharArray();
        int left = 0, right = s.length() - 1;
        String vowels = "aeiouAEIOU";

        // 3. Loop through the string
        while (left < right){
            while (left <= right && vowels.indexOf(str[left]) == -1) left++;
            while (left <= right && vowels.indexOf(str[right]) == -1) right--;

            if (left < right){
                char temp = str[left];
                str[left] = str[right];
                str[right] = temp;
                left ++;
                right --;
            }
        }

        return new String(str);
    }
}

[songyy5517]

2024/5/8 2024/5/9

• 双指针遍历循环的条件：left < right 不能是 <=