ReverseVowelsOfAString [source code]

public class ReverseVowelsOfAString {
static
/******************************************************************************/
public class Solution {
    public String reverseVowels(String s) {
        char[] letters = s.toCharArray();
        int n = letters.length;
        if (n == 0) return "";
        int tail = 0;
        int[] indices = new int[n];
        for (int i = 0; i < n; i++) {
            if ("aeiouAEIOU".indexOf(letters[i]) != -1) indices[tail++] = i;
        }
    tail--;
        int head = 0;
        while (head < tail) {
            swap(letters, indices[head++], indices[tail--]);
        }
        return String.valueOf(letters);
    }

    private void swap(char[] letters, int head, int tail) {
        char tmp = letters[head];
        letters[head] = letters[tail];
        letters[tail] = tmp;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ReverseVowelsOfAString.Solution tester = new ReverseVowelsOfAString.Solution();
        String[] inputs = {"hello", "leetcode", "aA"};
        for (String s : inputs) System.out.printf("%s -> %s%n", s, tester.reverseVowels(s));
    }
}

总体来说是一个不难的问题, 就是一些长期积累的小技巧的应用. 最后的速度是6ms (79%), 还算可以;

字母问题脑子里要有一根弦: 大小写; 这里我刚开始的时候就是没有想到这个问题, 被一个 case 给 break 了;

这里使用到的小技巧有:

• end pointer: 这个在 array 类的复制操作当中尤其常用; 这里用这个还有一个好处就是这个 pointer 直接在第二个循环, 也就是实际的 swap 的过程中正好可以继续二次利用, 虽然在利用之前要做一次--;
• String 查询; 这里判断 i 是vowel 当然可以用一连串的==, 但是这里的用法是用看起来更简短的string.contains来完成; 速度上其实不一定占优, 不过代码好看很多;
• char array to string, 这个也是讲过的了, valueOf 速度比 new String快很多;

这个是 submission 最优解:5(85)

public class Solution {  
    public String reverseVowels(String s) {  
        String vowel = "aeiouAEIOU";  
        char[] c = s.toCharArray();  
        int head = 0, tail = s.length() - 1;  
        while(head < tail) {  
            while(head < tail && vowel.indexOf(c[head]) < 0)  
                head++;  
            while(head < tail && vowel.indexOf(c[tail]) < 0)  
                tail--;  
            if(head < tail) {  
                char t = c[head];  
                c[head] = c[tail];  
                c[tail] = t;  
                head++; tail--;  
            }  
        }  
        return new String(c);  
    }  
}

总体思路是很类似的, 不过他这里使用了一个技巧, 没有专门单独把所有的 vowel 的 index 先记录下来, 而是直接就在原来的 array 上面操作, 用两个循环来控制 iteration 的移动;
我给他最后的 return 换成 valueOf 之后并没有明显的加速;

看了一下 discussion, 好像没有比这个更好的解法了;

Problem 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".

Difficulty:Easy
Category:Algorithms
Acceptance:38.32%
Contributor: LeetCode
Companies
google
Related Topics
two pointers string
Similar Questions
Reverse String