345. Reverse Vowels of a String

  • 38.6%

https://leetcode.com/problems/reverse-vowels-of-a-string/description/

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

1
2
3
4
5
Example 1:
Given s = "hello", return "holle".

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

Note:

The vowels does not include the letter “y”.


方法一:

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
string reverseVowels(string s) {
if(s.empty()) return s;
unordered_set<char> set = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
int i=0, j=s.size()-1;
while(i<j){
while(i<j && set.find(s[i])==set.end()) i++;
while(i<j && set.find(s[j])==set.end()) j--;
swap(s[i++], s[j--]);
}
return s;
}
};

方法二:

使用find_first_of和find_last_of函数,效果更好。

12ms, , April.24th, 2016

https://leetcode.com/discuss/99047/super-clean-solution-using-find_first_of-and-find_last_of

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
string reverseVowels(string s) {
int i = 0, j = s.size() - 1;
while (i < j) {
i = s.find_first_of("aeiouAEIOU", i);
j = s.find_last_of("aeiouAEIOU", j);
if (i < j) swap(s[i++], s[j--]);
}
return s;
}
};

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
string reverseVowels(string s) {
if(s.empty()) return s;
int i=0, j=s.size()-1;
while(i<j){
i = s.find_first_of("aeiouAEIOU", i);
j = s.find_last_of("aeiouAEIOU", j);
if(i<j) swap(s[i++], s[j--]); // 更新之后,要改变i和j的值,不能忘了
}
return s;
}
};

python

Solution mine:

144ms, , April.24th, 2016

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def reverseVowels(self, s):
"""
:type s: str
:rtype: str
"""
l = 0
r = len(s) - 1
s = list(s)
vowels = 'aeiouAEIOU'
while l < r:
if s[l] in vowels and s[r] in vowels:
s[l], s[r] = s[r], s[l]
l += 1
r -= 1
elif s[l] not in vowels:
l += 1
else:
r -= 1
return ''.join(s)

104ms, ,April.24th, 2016

https://leetcode.com/discuss/98983/python-2-pointers-solution

Python 2 Pointers Solution

The idea is really simple. But I think my code is somewhat ugly in two ways:

Convert string to list then convert back

Pointer processing is verbose.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def reverseVowels(self, s):
vowels = set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'])
s = list(s)
ptr_1, ptr_2 = 0, len(s) - 1
while ptr_1 < ptr_2:
if s[ptr_1] in vowels and s[ptr_2] in vowels:
s[ptr_1], s[ptr_2] = s[ptr_2], s[ptr_1]
ptr_1 += 1
ptr_2 -= 1
if s[ptr_1] not in vowels:
ptr_1 += 1
if s[ptr_2] not in vowels:
ptr_2 -= 1
return ''.join(s)

java

https://discuss.leetcode.com/topic/43412/java-standard-two-pointer-solution

In the inner while loop, don’t forget the condition “start less than end” while incrementing start and decrementing end. This is my friend’s google phone interview question. Cheers!

update! May use a HashSet to reduce the look up time to O(1)

19ms, 17.67%

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
27
public class Solution {
public String reverseVowels(String s) {
if(s == null || s.length()==0) return s;
String vowels = "aeiouAEIOU";
char[] chars = s.toCharArray();
int start = 0;
int end = s.length()-1;
while(start<end){

while(start<end && !vowels.contains(chars[start]+"")){
start++;
}

while(start<end && !vowels.contains(chars[end]+"")){
end--;
}

char temp = chars[start];
chars[start] = chars[end];
chars[end] = temp;

start++;
end--;
}
return new String(chars);
}
}

谢谢你,可爱的朋友。