LeetCode 917. 仅仅反转字母
目录
题目描述
题意分析
给一个字符串，把其中的英文字母按顺序整体反转，而所有非字母字符（数字、标点、下划线等）留在原来的下标位置不动。返回改造后的字符串。
题干只有一句话，但藏着两个必须分清的对象：位置和内容。非字母字符的位置是固定的骨架，字母则像流水一样在这些骨架的空隙里从两端往中间对调。举例说，
"a-bC-dEf-ghIj"中所有的-保持在下标 1、4、8 不动，剩下的字母序列abCdEfghIj反转成jIhgfEdCba后依次填回空位，得到"j-Ih-gfE-dCba"。「大小写都算字母且反转时不改变大小写」这一点容易看漏：
C反转后仍然是大写的C，只是换了个位置。所以判定函数只负责区分「是不是字母」，不做任何转换。约束里串长最多 100，字符是 ASCII 可见字符且不含引号，规模极小。这说明本题考的不是复杂度，而是双指针在带跳过条件时的边界控制——什么时候推进、什么时候交换、循环怎么终止。
边界：全是非字母时原样返回；只有一个字母时它自己反转还是它自己；空串或长度为 1 直接返回。这些都应当由主循环自然覆盖。
解法：双指针原地交换
核心思路
最直接的想法是分三步：先把所有字母抽出来存进一个列表，反转这个列表，再从左到右扫描原串，遇到字母就从列表里按顺序取一个填回去。这个做法思路清晰、绝不会错，但要额外开一个 $O(n)$ 的容器，还要扫两遍。
瓶颈在于我们把「抽取」和「回填」拆成了两个阶段，中间必须有地方存放。但仔细看反转的本质：反转就是把第一个字母和最后一个字母对调、第二个和倒数第二个对调…… 既然是两两对调，完全可以原地进行，一次扫描搞定，不需要中间容器。
于是用左右双指针：
l从左端出发找下一个字母，r从右端出发找上一个字母，两者都停在字母上时交换它们，然后各自向内跨一步。非字母字符在这个过程中从未被交换过，位置自然保持不变——它们只是被跳过，而不是被处理。不变量：每轮外层循环开始时，下标区间
[0, l)与(r, n-1]里的字母已经处于最终位置，而[l, r]区间内的字母还保持原始相对顺序；所有非字母字符自始至终没有移动过。每次交换把区间两端各一个字母定位好，区间随之收窄，l >= r时全部完成。判定「是不是字母」直接用
Character.isLetter（Go 版手写范围判断），因为题目保证输入是 ASCII，判定只需覆盖a-z与A-Z两段。这一步没有任何隐藏语义，不必引入正则或大小写转换。实现上用
char[]而不是反复拼接字符串：Java 与 Go 的字符串都不可变，逐字符改写只能落在字符数组上，最后再一次性构造结果。
解题步骤
- 转成字符数组，初始化
l = 0、r = n - 1：字符串不可变，原地交换必须在数组上做。两个指针分别从两端向内收敛。- 外层循环条件
l < r：用严格小于而不是小于等于。两者相等时指向同一个字符，自己和自己交换毫无意义，还会白白多走一轮。- 内层推进
l跳过非字母：while (l < r && !isLetter(a[l])) l++。内层条件里必须带上l < r，否则在"---"这种全非字母的串上，l会一路冲过r直到越界。- 内层推进
r跳过非字母：与上一步对称。注意两个内层循环要分开写，不能合并成一个条件——它们各自的推进方向和判定对象都不同。- 交换前再判一次
l < r：两个内层循环跑完后，指针可能已经在中间相遇（比如中间那段全是非字母），此时不该交换。这个if是防御，也是让l++、r--只在真正完成一次交换后才执行。- 交换并同时内移：
swap(a[l], a[r])后l++、r--。两个指针必须同时移动——只动一个会让下一轮重复处理同一个字母，甚至把刚换好的字符又换回去。- 返回
new String(a)：一次性构造，避免在循环里做字符串拼接。以
s = "a-bC-dEf-ghIj"走一遍（长度 13，下标 0 到 12）。字符依次是a - b C - d E f - g h I j。初始
l = 0、r = 12。第 1 轮：
a[0] = 'a'是字母，l不动；a[12] = 'j'是字母，r不动。l < r成立，交换得j-bC-dEf-ghIa，l = 1、r = 11。第 2 轮：
a[1] = '-'非字母，l推进到 2（a[2] = 'b'是字母停下）；a[11] = 'I'是字母，r不动。交换下标 2 与 11 得j-IC-dEf-ghba，l = 3、r = 10。注意下标 1 的-被跳过后就再也不会被触碰，它永远留在这里。第 3 轮：
a[3] = 'C'是字母；a[10] = 'h'是字母。交换得j-Ih-dEf-gCba，l = 4、r = 9。第 4 轮：
a[4] = '-'非字母，l推进到 5（'d'）；a[9] = 'g'是字母。交换得j-Ih-gEf-dCba，l = 6、r = 8。第 5 轮：
a[6] = 'E'是字母；a[8] = '-'非字母，r退到 7（'f'）。此时l = 6 < r = 7，交换得j-Ih-gfE-dCba，l = 7、r = 6。第 6 轮：
l = 7、r = 6，l < r不成立，循环退出。返回"j-Ih-gfE-dCba"，与预期一致。再看内层条件为什么必须带
l < r：对s = "---"，l = 0、r = 2进入循环，若内层写成while (!isLetter(a[l])) l++，l会一路走到 3 并访问a[3]，直接数组越界。带上l < r后l停在 2，随后r的内层因l < r已不成立而不动，最外层的if (l < r)也不成立，循环平安结束，原样返回"---"。
代码实现
class Solution {
public String reverseOnlyLetters(String s) {
char[] a = s.toCharArray();
int l = 0;
int r = a.length - 1;
while (l < r) {
while (l < r && !Character.isLetter(a[l])) {
l++;
}
while (l < r && !Character.isLetter(a[r])) {
r--;
}
if (l < r) {
char tmp = a[l];
a[l] = a[r];
a[r] = tmp;
l++;
r--;
}
}
return new String(a);
}
}
func reverseOnlyLetters(s string) string {
a := []byte(s)
l, r := 0, len(a)-1
for l < r {
for l < r && !isLetter(a[l]) {
l++
}
for l < r && !isLetter(a[r]) {
r--
}
if l < r {
a[l], a[r] = a[r], a[l]
l++
r--
}
}
return string(a)
}
func isLetter(c byte) bool {
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
}
复杂度分析
- 时间复杂度：$O(n)$。
l只增、r只减，两者合起来在数组上走过一遍就相遇；内层的跳过循环推进的是同一对指针，不构成嵌套开销。- 空间复杂度：$O(n)$（Java 与 Go 都需要一份
char[]/[]byte副本，因为字符串不可变），交换本身只用一个临时变量。若语言支持可变字符串（如 C 的char*），可做到 $O(1)$ 额外空间。
关键点总结
- 「保留某类元素位置不变、只重排另一类」的题，通用手法是让指针跳过不参与的元素而非搬动它们——不动就是最好的保持。
- 反转等价于两端逐对交换，因此可以原地完成，不需要「先抽取再回填」的中间容器；识别出这一点就省掉一个 $O(n)$ 结构和一趟扫描。
- 内层跳过循环必须带上
l < r的越界保护，这是全题最容易崩的一行；全非字母的输入就是它的反例。- 交换后两个指针必须同时内移，否则会重复处理同一位置甚至把已完成的交换撤销。
- 大小写不做转换：判定只回答「是不是字母」，
C换位后依然是C。混入toLowerCase会静默改变输出内容。- 面试视角：这题的价值全在边界。写完后主动用
"---"、"a"、"ab-"三个用例口述验证一遍，比多写十行代码更能体现工程素养。
易错点总结
- 内层跳过循环不带
l < r："---"会让l一路推到下标 3 并访问a[3]，数组越界异常。- 交换前不再判一次
l < r："a-"中l停在 0、r从 1 退到 0，若无这层判断会执行swap(a[0], a[0])并让l变 1、r变 -1，虽然结果侥幸正确，但同类输入"-a-"会多做无意义操作，逻辑上不成立。- 外层条件写成
l <= r：奇数个字母时中间那个字母会与自己交换，随后l与r交错，多跑一轮；若内层保护又不严，会连带越界。- 交换后只移动一个指针：
"ab"中若只l++，下一轮l = 1、r = 1，外层退出还算侥幸；但"abc"中会把已换好的字符再换回去，输出仍是"abc"。- 把非字母字符也纳入交换：
"a-b"会输出"b-a"（巧合正确），但"ab-"会输出"-ba"，而正确答案是"ba-"——分隔符的位置被挪动了。- 判定函数漏掉大写字母：只判
c >= 'a' && c <= 'z'，"a-bC-dEf"中的C、E会被当成非字母跳过，输出"f-bC-dEa"之类的错误结果。- 用
Character.isLetterOrDigit代替isLetter："a1b"中数字 1 会被当作可反转元素，输出"b1a"看似正确，但"ab1"会输出"1ba"，数字位置被改变，正确答案是"ba1"。- 在循环里用字符串拼接构造结果：
s = s.substring(0,l) + ...每次都新建字符串，复杂度退化到 $O(n^2)$，且极易把下标算错。- 顺手做了大小写转换：加了
toLowerCase后"a-bC-dEf-ghIj"会输出"j-ih-gfe-dcba"，字符内容被篡改。- 误以为要反转整个字符串：
"a-bC"会输出"Cb-a"，非字母的-从下标 1 跑到了下标 2，与题意「非字母不动」直接冲突。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 344. 反转字符串 | 简单 | 无跳过条件的纯双指针交换，是本题去掉筛选后的骨架 |
| 345. 反转字符串中的元音字母 | 简单 | 筛选条件从「是字母」换成「是元音」，还要兼顾大小写元音 |
| 125. 验证回文串 | 简单 | 同样跳过非字母数字，但只比较不交换，且需统一大小写 |
| 557. 反转字符串中的单词 III | 简单 | 按空格切段后各段内部反转，考的是段边界的定位 |
| 151. 反转字符串中的单词 | 中等 | 整体反转再逐词反转，还要压缩多余空格，边界比本题复杂得多 |
| 541. 反转字符串 II | 简单 | 每 2k 个字符反转前 k 个，重点是尾部不足 k 时的处理 |