LeetCode 917. 仅仅反转字母
题目描述
题意分析
只反转字符串中英文字母出现的顺序，数字、标点等非字母仍留在原下标。大小写属于字母本身，移动时不做转换；题目输入只包含 ASCII 字符。
解法：字符副本 + 双指针
核心思路
[!blue]
如果把所有字母单独取出，目标就是反转这个字母序列，再放回原来的字母位置。无需真正建立这个中间序列，只要每次交换尚未处理的第一个和最后一个字母，就能直接完成同样的配对。
先把字符串转成可修改的字符或字节数组，用
l、r从两端向内移动。左边遇到非字母就只移动l，右边遇到非字母就只移动r；两边都停在字母上时交换它们，然后同时向内一步。每次交换都把待处理字母序列的两端放到最终位置，区间外的字母不再改动，而非字母从未参与交换，始终留在原位。指针相遇时最多剩一个中间字母，本来就无需移动；若只剩非字母，跳过后也会相遇。因此处理到
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)$，两端指针只向中间移动。
- 空间复杂度：$O(n)$，保存可修改数组和结果字符串。
关键点总结
[!green]
- 移动的是字母内容，非字母下标固定。
- 大小写属于字符自身，不做转换。
- 跳过非字母时也要检查边界。
易错点总结
[!yellow]
- 反转整个数组：非字母会移动位置。
- 只识别小写字母：大写字母被错误保留在原位。
- 把数字也当作字母：数字位置不再保持。
- 跳过非字母时不检查边界：全非字母字符串可能越界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 345. 反转字符串中的元音字母 | 简单 | 同样跳过不参与反转的位置，原题仅反转元音，本题反转所有字母。 |
| 344. 反转字符串 | 简单 | 普通区间反转的双指针可复用，本题在交换前多一步字符类别筛选。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！