LeetCode 345: Reverse Vowels of a String (Two Pointers + Vowel Set)
LeetCode 345Two PointersStringToday we solve LeetCode 345 - Reverse Vowels of a String.
Source: https://leetcode.com/problems/reverse-vowels-of-a-string/
English
Problem Summary
Given a string s, reverse only the vowels and keep all consonants in place. Return the transformed string.
Key Insight
Use two pointers: one from the left and one from the right. Move each pointer until it lands on a vowel, then swap these two vowels and continue inward.
The set of vowels is fixed: a,e,i,o,u,A,E,I,O,U. Membership checks should be O(1).
Brute Force and Limitations
A brute-force approach can collect all vowels first and then write them back in reverse order. It works but needs extra storage for the vowel list. Two pointers perform swaps in place with lower auxiliary memory.
Optimal Algorithm Steps
1) Convert string to mutable char array.
2) Set l=0, r=n-1.
3) Advance l while not vowel; decrease r while not vowel.
4) If l < r, swap chars and move both pointers.
5) Convert array back to string.
Complexity Analysis
Time: O(n), each pointer moves at most n times.
Space: O(n) in languages with immutable strings (char-array copy); extra working space besides output is O(1).
Common Pitfalls
- Forgetting uppercase vowels.
- Swapping before both pointers point to vowels.
- Not moving pointers after swap, causing infinite loops.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
private boolean isVowel(char c) {
return "aeiouAEIOU".indexOf(c) >= 0;
}
public String reverseVowels(String s) {
char[] arr = s.toCharArray();
int l = 0, r = arr.length - 1;
while (l < r) {
while (l < r && !isVowel(arr[l])) l++;
while (l < r && !isVowel(arr[r])) r--;
char tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;
l++;
r--;
}
return new String(arr);
}
}func reverseVowels(s string) string {
arr := []rune(s)
isVowel := func(c rune) bool {
switch c {
case 'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U':
return true
default:
return false
}
}
l, r := 0, len(arr)-1
for l < r {
for l < r && !isVowel(arr[l]) {
l++
}
for l < r && !isVowel(arr[r]) {
r--
}
arr[l], arr[r] = arr[r], arr[l]
l++
r--
}
return string(arr)
}class Solution {
public:
bool isVowel(char c) {
static string v = "aeiouAEIOU";
return v.find(c) != string::npos;
}
string reverseVowels(string s) {
int l = 0, r = (int)s.size() - 1;
while (l < r) {
while (l < r && !isVowel(s[l])) l++;
while (l < r && !isVowel(s[r])) r--;
swap(s[l], s[r]);
l++;
r--;
}
return s;
}
};class Solution:
def reverseVowels(self, s: str) -> str:
arr = list(s)
vowels = set("aeiouAEIOU")
l, r = 0, len(arr) - 1
while l < r:
while l < r and arr[l] not in vowels:
l += 1
while l < r and arr[r] not in vowels:
r -= 1
arr[l], arr[r] = arr[r], arr[l]
l += 1
r -= 1
return "".join(arr)/**
* @param {string} s
* @return {string}
*/
var reverseVowels = function(s) {
const arr = s.split('');
const vowels = new Set(['a','e','i','o','u','A','E','I','O','U']);
let l = 0, r = arr.length - 1;
while (l < r) {
while (l < r && !vowels.has(arr[l])) l++;
while (l < r && !vowels.has(arr[r])) r--;
[arr[l], arr[r]] = [arr[r], arr[l]];
l++;
r--;
}
return arr.join('');
};中文
题目概述
给你一个字符串 s，只反转其中的元音字母，其他字符位置保持不变，返回结果字符串。
核心思路
使用双指针：左指针从前往后找元音，右指针从后往前找元音。两边都命中后交换，然后继续向中间收缩。
元音集合固定为 a,e,i,o,u,A,E,I,O,U，判断是否元音应为常数时间。
暴力解法与不足
暴力做法可以先把全部元音收集出来，再倒序写回。虽然可行，但要额外存储元音列表。双指针可以原地交换，辅助空间更小。
最优算法步骤
1）把字符串转成可修改字符数组。
2）初始化 l=0、r=n-1。
3）左指针跳过非元音，右指针跳过非元音。
4）若 l < r 则交换并同时移动两指针。
5）最后把字符数组转回字符串。
复杂度分析
时间复杂度：O(n)，每个指针最多走一遍。
空间复杂度：在字符串不可变语言中为 O(n)（字符数组副本），除输出外额外工作空间为 O(1)。
常见陷阱
- 漏掉大写元音。
- 指针还没落在元音就直接交换。
- 交换后不推进指针，导致死循环。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
private boolean isVowel(char c) {
return "aeiouAEIOU".indexOf(c) >= 0;
}
public String reverseVowels(String s) {
char[] arr = s.toCharArray();
int l = 0, r = arr.length - 1;
while (l < r) {
while (l < r && !isVowel(arr[l])) l++;
while (l < r && !isVowel(arr[r])) r--;
char tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;
l++;
r--;
}
return new String(arr);
}
}func reverseVowels(s string) string {
arr := []rune(s)
isVowel := func(c rune) bool {
switch c {
case 'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U':
return true
default:
return false
}
}
l, r := 0, len(arr)-1
for l < r {
for l < r && !isVowel(arr[l]) {
l++
}
for l < r && !isVowel(arr[r]) {
r--
}
arr[l], arr[r] = arr[r], arr[l]
l++
r--
}
return string(arr)
}class Solution {
public:
bool isVowel(char c) {
static string v = "aeiouAEIOU";
return v.find(c) != string::npos;
}
string reverseVowels(string s) {
int l = 0, r = (int)s.size() - 1;
while (l < r) {
while (l < r && !isVowel(s[l])) l++;
while (l < r && !isVowel(s[r])) r--;
swap(s[l], s[r]);
l++;
r--;
}
return s;
}
};class Solution:
def reverseVowels(self, s: str) -> str:
arr = list(s)
vowels = set("aeiouAEIOU")
l, r = 0, len(arr) - 1
while l < r:
while l < r and arr[l] not in vowels:
l += 1
while l < r and arr[r] not in vowels:
r -= 1
arr[l], arr[r] = arr[r], arr[l]
l += 1
r -= 1
return "".join(arr)/**
* @param {string} s
* @return {string}
*/
var reverseVowels = function(s) {
const arr = s.split('');
const vowels = new Set(['a','e','i','o','u','A','E','I','O','U']);
let l = 0, r = arr.length - 1;
while (l < r) {
while (l < r && !vowels.has(arr[l])) l++;
while (l < r && !vowels.has(arr[r])) r--;
[arr[l], arr[r]] = [arr[r], arr[l]];
l++;
r--;
}
return arr.join('');
};
Comments