345.md

345. Reverse Vowels of a String

Description

Write a function that takes a string as input and reverse only the vowels of a string

Example 1: Given s = "hello", return "holle".

Example 2: Given s = "leetcode", return "leotcede".

Note: The vowels does not include the letter "y".

Thinking Process

1. Use two pointers pointing the vowels that are closest to the head and the tail of the string respectively
2. Swap the characters at the two pointers and update the pointers
3. Repeat until the pointers meet

Code

public class Solution {
    public String reverseVowels(String s) {
        char[] word = s.toCharArray();
        int low = 0;
        int high = word.length - 1;
        String vowels = new String("aeiouAEIOU");
        
        while(low < high){
            while(low < high && vowels.indexOf(word[low]) < 0)
                low++;
            while(low < high && vowels.indexOf(word[high]) < 0)
                high--;
            char temp = word[low];
            word[low++] = word[high];
            word[high--] = temp;
        }
        return new String(word);
    }
}

Complexity

1. Time complexity is O(n) as each char in the string is visited once
2. Space complexity is O(n)