問題：
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".
大意：
寫一個函數(shù)硫豆，輸入一個字符串然后翻轉里面的元音字母。
例1：
給出 s = "hello"笼呆，返回"holle"熊响。
例2：
給出 s = "leetcode"，返回"leotcede"诗赌。
注意：
元音不包括字母“y”汗茄。
思路：
首先想到的一個思路是遍歷字符串中每個字母，遇到元音字母就記錄下字母和所在的位置铭若。遍歷完后洪碳，對著記錄下來的元音字母，將字符串中的元音按照反序替換一遍就好了叼屠，這種做法也做出來了瞳腌，但是結果非常耗時，花了200多ms镜雨。
后來想到了第二種方法嫂侍，在字符串的頭和尾都放一個指針進行遍歷，兩端向中間去遍歷，當兩端都遇到元音字母后挑宠，就對換菲盾。直到兩個指針碰頭為止。這個方法就快多了各淀，同時優(yōu)化一下檢查是否是元音字母的方法懒鉴，只需要幾ms就搞定了。
需要注意的是題目中并沒有說字符串是純大寫或者小寫碎浇，所以大小寫都要考慮临谱，這個容易忽略。
代碼1（Java）：
public class Solution {
public String reverseVowels(String s) {
int[] vowelIndex = new int[s.length()];
char[] vowelChar = new char[s.length()];
int index = 0;// 標記上面兩個數(shù)組記錄的位置
// 記錄元音字母及出現(xiàn)的位置
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == 'a' || s.charAt(i) == 'e' || s.charAt(i) == 'i' || s.charAt(i) == 'o' || s.charAt(i) == 'u' || s.charAt(i) == 'A' || s.charAt(i) == 'E' || s.charAt(i) == 'I' || s.charAt(i) == 'O' || s.charAt(i) == 'U') {
vowelChar[index] = s.charAt(i);
vowelIndex[index] = i;
index++;
}
}
// 替換元音字母位置
if (index == 0) return s;
else {
StringBuffer buffer = new StringBuffer(s);
for (int i = 0; i < index; i++) {
buffer.replace(vowelIndex[i], vowelIndex[i]+1, String.valueOf(vowelChar[index-i-1]));
}
return buffer.toString();
}
}
}
代碼2（Java）：
public class Solution {
static final String vowels = "aeiouAEIOU";
public String reverseVowels(String s) {
int first = 0, last = s.length() - 1;
char[] array = s.toCharArray();
while(first < last){
// 正向找元音
while(first < last && vowels.indexOf(array[first]) == -1){
first++;
}
// 逆向找元音
while(first < last && vowels.indexOf(array[last]) == -1){
last--;
}
// 對換
char temp = array[first];
array[first] = array[last];
array[last] = temp;
first++;
last--;
}
return new String(array);
}
}
代碼（C++）
class Solution {
public:
string reverseVowels(string s) {
vector<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
int len = s.length();
bool i_found = false;
bool j_found = false;
for (int i = 0, j = 1; i + j < len;) {
if (find(vowels.begin(), vowels.end(), s[i]) == vowels.end()) {
i++;
continue;
} else {
i_found = true;
if (j_found) {
char temp = s[i];
s[i] = s[len-j];
s[len-j] = temp;
i_found = false;
j_found = false;
i++;
j++;
continue;
}
}
if (find(vowels.begin(), vowels.end(), s[len-j]) == vowels.end()) {
j++;
continue;
} else {
j_found = true;
if (i_found) {
char temp = s[i];
s[i] = s[len-j];
s[len-j] = temp;
i_found = false;
j_found = false;
i++;
j++;
continue;
}
}
}
return s;
}
};
合集：https://github.com/Cloudox/LeetCode-Record
