345 Reverse Vowels of a String

1. Question

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

2. Implementation

(1) Two Pointers
1
class Solution {
2
public String reverseVowels(String s) {
3
if (s == null || s.length() == 0) {
4
return s;
5
}
6
7
String vowels = "aeiouAEIOU";
8
9
char[] letters = s.toCharArray();
10
int start = 0, end = s.length() - 1;
11
12
while (start < end) {
13
while (start < end && vowels.indexOf(letters[start]) < 0) {
14
++start;
15
}
16
17
while (start < end && vowels.indexOf(letters[end]) < 0) {
18
--end;
19
}
20
21
if (start >= end) {
22
break;
23
}
24
25
swap(letters, start, end);
26
++start;
27
--end;
28
}
29
return new String(letters);
30
}
31
32
public void swap(char[] letters, int start, int end) {
33
char temp = letters[start];
34
letters[start] = letters[end];
35
letters[end] = temp;
36
}
37
}
Copied!

3. Time & Space Complexity

Two Pointers: 时间复杂度O(n), 空间复杂度O(1)