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”.

O(n) time O(n) space reverse first solution

Seems this is the fastest solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public String reverseVowels(String s) {
        if (s == null || s.length() == 0) return s;
        char[] input = s.toCharArray();
        int left = 0, right = s.length() - 1;
        String vowels = "aeiouAEIOU";
        while (left < right) {
            if (!isVowel(input[left], vowels)) {
                left++;
            } else if (!isVowel(input[right], vowels)) {
                right--;
            } else {
                char temp = input[left];
                input[left] = input[right];
                input[right] = temp;
                left++;
                right--;
            }
        }
        return new String(input);
    }
    
    public boolean isVowel(char c, String vowels) {
        return vowels.indexOf(c) == -1 ? false : true;
    }
}

O(n) time O(n) space StringBuilder solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public String reverseVowels(String s) {
        StringBuilder sb = new StringBuilder();
        String vowels = "AEIOUaeiou";
        int j = s.length() - 1;
        for (int i = 0; i < s.length(); i++) {
            if (vowels.indexOf(s.charAt(i)) != -1) {
                while (j >= 0 && vowels.indexOf(s.charAt(j)) == -1) {
                    j--;
                }
                sb.append(s.charAt(j));
                j--;
            } else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}