345. Reverse Vowels of a String

Leetcode Two Pointers String

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

Example 1:

Input: "hello"
Output: "holle"

Example 2:

Input: "leetcode"
Output: "leotcede"

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

分析

首先，需要了解英文字母里面的元音字母一共有A, E, I, O, and U。这道题目思路还是非常直接的。就是从左右开始分别寻找元音字母，如果找到它们则相互交换。

第一个问题是如何确认该字母是元音字母。首先想到的是可以把所有字母放在HashSet中，然后查询HashSet。

Set<Character> vowels = new HashSet<>(
        Arrays.asList('A', 'E', 'I', 'O', 'U',
                'a', 'e', 'i', 'o', 'u'));
vowels.contains(char);

另一种方案是用Switch匹配

public static boolean isVowel(char a){
    switch(a){
        case ('a') : return true;
        case ('e') : return true;
        case ('i') : return true;
        case ('o') : return true;
        case ('u') : return true;
        case ('A') : return true;
        case ('E') : return true;
        case ('I') : return true;
        case ('O') : return true;
        case ('U') : return true;
        default : return false;
    }
}

结果显示用Switch匹配更快一些，前面方案用时7ms，后面方案用时5ms。

然后就是寻找元音字母了。这个其实是非常简单的，主要是细节问题，注意下标的处理。寻找元音字母的过程其实和快排的Partition过程非常类似，可以说几乎一摸一样。

int n = s.length() - 1;
int left = 0, right = n;
while (true) {
    // find vowels
    while (!isVowel(charArray[left++]))
        if (left == n) return new String(charArray);
    while (!isVowel(charArray[right--])) { }

    // check if two pointers cross
    if (--left >= ++right)
        break;

    // exchange them
    temp = charArray[right];
    charArray[right] = charArray[left];
    charArray[left] = temp;
    left++;
    right--;
}

最后的问题就是字符串的表示以及返回。这里我也想到了几种方案，并进行了比较。第一种方案是使用StringBuilder，首先新建一个与原始字符串相同的StringBuilder，然后每次要交换时都进行替换。

StringBuilder res = new StringBuilder(s);
// exchange them
res.replace(left, left + 1, String.valueOf(charArray[right]));
res.replace(right, right + 1, String.valueOf(charArray[left]));

这种方案的效率非常低！运行时间需要170ms，整整慢了几十倍。

另一种方案是直接使用char Array，由于是in-place replacement，而且没有额外对象的开销，速度非常快。

最后我使用的方案，击败了100%的人。

public String reverseVowels(String s) {
    if (s.length() < 2) return s;
    char[] charArray = s.toCharArray();
    char temp;
    int n = s.length() - 1;
    int left = 0, right = n;
    while (true) {
        // find vowels
        while (!isVowel(charArray[left++]))
            if (left == n) return new String(charArray);
        while (!isVowel(charArray[right--])) { }

        // check if two pointers cross
        if (--left >= ++right)
            break;

        // exchange them
        temp = charArray[right];
        charArray[right] = charArray[left];
        charArray[left] = temp;
        left++;
        right--;
    }
    return new String(charArray);
}

    public static boolean isVowel(char a){
    switch(a){
        case ('a') : return true;
        case ('e') : return true;
        case ('i') : return true;
        case ('o') : return true;
        case ('u') : return true;
        case ('A') : return true;
        case ('E') : return true;
        case ('I') : return true;
        case ('O') : return true;
        case ('U') : return true;
        default : return false;
    }
}