LeetCode 345. 反转字符串中的元音字母
目录
题目描述
题意分析
给定字符串 s，只把其中的元音字母按相反顺序重排，其余字符必须留在原来的位置上，返回改造后的字符串。
题面明确写了元音包括
a、e、i、o、u，且大小写都算。这一句是最容易读漏的约束，样例 "Hello" 里的大写 O 就是专门用来卡这一点的。输入长度最大 3 × 10^5，字符可以是任意可打印 ASCII，不只是字母。所以判断函数不能写成「不是辅音就是元音」，必须显式列出那十个字符。
把要求换个说法会更清楚：取出所有元音构成的子序列，把它整体倒过来，再按原来的下标依次放回去。非元音位置从头到尾不动，元音位置的集合也不变，变的只是里面装的字符。
边界要覆盖：没有元音（结果与输入相同）、只有一个元音（同样不变）、以及全是元音（等价于整串反转）。
解法：左右指针交换元音
核心思路
按上面那个说法直译，最容易想到的是两趟：第一趟把所有元音和它们的下标收集到数组里，第二趟把元音数组反转后按下标写回。这个做法完全正确，但要额外开一个最长为 n 的数组，也要写两个循环。
瓶颈在于「先全部收集再统一回填」这个中间环节其实是多余的。反转一个序列等价于把首尾元素两两对调，而这件事不需要先把序列物化出来，只要能按顺序找到「从左数第 i 个元音」和「从右数第 i 个元音」，直接就地交换即可。
于是用两个指针从两端相向推进，各自跳过非元音。整趟扫描维持的不变量是：区间 [0, left) 和 (right, n - 1] 里的元音都已经落到最终位置上，且这两段里已完成配对的元音数量相同；剩下待处理的部分永远是闭区间 [left, right]。
每轮把 left 停在从左侧数的第一个未处理元音、right 停在从右侧数的第一个未处理元音，交换二者后两个指针各向内移动一格，不变量随之推进一层。当 left 和 right 相遇或交错时，剩余区间里不足两个待配对元音，中间那个（若存在）本来就应该待在原地，直接结束。
判断元音的部分单独抽成一个小函数，把十个字符显式列全，避免在主循环里堆一长串比较。
解题步骤
- 先把字符串转成字符数组，并令 left = 0、right = n - 1。Java 和 Go 的字符串都不可变，只有转成数组才能就地交换。
- 外层循环条件是
left < right。用严格小于是因为两个指针指向同一位置时，那个字符没有配对对象，不需要任何操作。- 进入循环后先让 left 向右跑，条件写成
left < right && !isVowel(chars[left])。这里必须带上left < right，否则当右半段全是非元音时 left 会一路冲出数组末尾。- 再让 right 向左跑，条件同理写成
left < right && !isVowel(chars[right])。两个内层循环都以「指针停在元音上，或者两指针已经碰头」结束。- 两个内层循环跑完后再判一次
left < right，成立才交换。这一次判断不能省：若两个指针在寻找过程中已经碰头，说明剩余区间里没有可配对的两个元音，此时交换会把同一个字符和自己换，虽然值不变但逻辑上已经越过了不变量。- 无论是否发生交换，都执行
left++和right--。已经配对过的两个位置不再需要考虑，而没配对的情形下两指针已经碰头，加减一只会让外层条件更快失效，不会出错。- 循环结束后把字符数组转回字符串返回。
以
s = "leetcode"走一遍：数组为 [l, e, e, t, c, o, d, e]，left = 0、right = 7。第一轮：left 上的l不是元音，前进到 1 停在e；right 上的e是元音，原地不动。left = 1 < right = 7，交换两个e，内容没变化但配对完成，随后 left = 2、right = 6。第二轮：left = 2 是e，直接停下；right = 6 是d，后退到 5 停在o。left = 2 < right = 5，交换e与o，数组变成 [l, e, o, t, c, e, d, e]，随后 left = 3、right = 4。第三轮：left = 3 是t不是元音，前进到 4；此时 left 已等于 right，内层条件失效停下；right 的内层循环因为同样的原因一步都不走。中间那次left < right判断为假，不交换，接着 left = 5、right = 3，外层条件失效退出。返回 "leotcede"，与样例一致。
代码实现
class Solution {
// 左右指针分别向中间寻找下一个元音，两个指针都停在元音上时再交换。
public String reverseVowels(String s) {
char[] chars = s.toCharArray();
int left = 0;
int right = chars.length - 1;
while (left < right) {
while (left < right && !isVowel(chars[left])) {
left++;
}
while (left < right && !isVowel(chars[right])) {
right--;
}
if (left < right) {
char swapValue = chars[left];
chars[left] = chars[right];
chars[right] = swapValue;
}
left++;
right--;
}
return new String(chars);
}
private boolean isVowel(char ch) {
return "aeiouAEIOU".indexOf(ch) >= 0;
}
}
func reverseVowels(s string) string {
// 左右指针分别向中间寻找下一个元音，两个指针都停在元音上时再交换。
chars := []byte(s)
left, right := 0, len(chars)-1
for left < right {
for left < right && !isVowel(chars[left]) {
left++
}
for left < right && !isVowel(chars[right]) {
right--
}
if left < right {
chars[left], chars[right] = chars[right], chars[left]
}
left++
right--
}
return string(chars)
}
func isVowel(ch byte) bool {
switch ch {
case 'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U':
return true
default:
return false
}
}
复杂度分析
- 时间复杂度：$O(n)$，left 只会向右走、right 只会向左走，两者移动步数之和不超过 n，每一步的元音判断是常数次比较。
- 空间复杂度：$O(n)$，来自不可变字符串复制出的字符数组；除此之外只有两个下标变量，若语言支持原地改字符串则为 $O(1)$。
关键点总结
- 「保持某些位置不动、只把另一些位置上的元素反转」这类题，都可以用相向双指针在原地完成，不必先把目标元素抽出来再回填。
- 内层的跳过循环一定要带上与外层相同的边界条件，否则一侧全是无关字符时指针会越界，这是相向双指针最常见的崩溃点。
- 交换前的那次
left < right复查，本质是在确认「剩余区间里确实还有两个待配对元素」，把它当成不变量的守卫来记比死背模板更牢。- 把「是否属于目标集合」抽成独立的判定函数，主循环就只剩指针推进逻辑；集合一变（比如改成数字、改成大写字母）只需要改一处。
- 面试视角：这题真正的采分点是边界处理和大小写覆盖，写完后主动说明「left、right 各自只走 n 步所以是线性」以及「用集合还是 switch 判元音各有什么权衡」比把代码写快更重要。
易错点总结
- 错误写法：内层跳过循环写成
while (!isVowel(chars[left])) left++而不带left < right→ s = "bcd" 全是辅音时 left 一路走出数组，直接下标越界。- 错误写法：判定函数只写小写元音 → s = "Hello" 里的大写
O不被识别，得到 "Hello" 原样返回，而正确答案是 "Holle"。- 错误写法：用「不是辅音字母就当元音」的反向判定 → 题目允许出现
!、.、数字等字符，它们会被误判成元音参与交换，位置全乱。- 错误写法：两个内层跳过循环跑完后不再复查
left < right就直接交换 → 指针在寻找途中碰头时会执行一次自己和自己的交换，虽然值没变，但如果交换写法带临时变量或位运算异或，自异或会把该字符清零。- 错误写法：把
left++和right--只写在交换成功的分支里 → 未发生交换时两个指针都不动，外层条件永远成立，直接死循环。- 错误写法：外层条件写成
left <= right→ 长度为奇数且中点是元音时，中点会和自己配对，再叠加上一条的异或写法就会出错；即便不出错也做了无谓的一轮。- 错误写法：对着原字符串用
s.charAt判断、却把结果写进一个新数组的对应位置 → 交换后再读原串会拿到旧字符，配对关系错乱，必须始终读写同一份数组。- 错误写法：先用
s.replaceAll之类的库函数把元音抽出来反转，再用正则逐个替换回去 → 替换是从左到右按次序生效的，中途的替换结果会被后续匹配再次命中，s = "aA" 这类输入会得到错误结果，而且这条路把双指针这个考点整个绕过了。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 151. 反转字符串中的单词 | 中等 | 先整体反转再逐词反转，还要压缩多余空格 |
| 186. 反转字符串中的单词 II | 中等 | 与 151 同思路但要求原地、额外空间 $O(1)$ |
| 344. 反转字符串 | 简单 | 最基础的相向双指针交换，可当本题的子过程 |
| 541. 反转字符串 II | 简单 | 按 2k 分组，右边界靠 min 合并尾部规则 |
| 557. 反转字符串中的单词 III | 简单 | 只反转每个单词内部，单词顺序保持不变 |
| 剑指 Offer 58 - I. 翻转单词顺序 | 简单 | 与 151 同题，注意首尾和中间的连续空格 |
| 补充题 11. 翻转URL字符串里的单词 | 中等 | 分隔符换成点号，反转逻辑不变但切分要改 |