【C++】字符串中的字母反转算法详解
引言
在处理字符串时，我们经常需要根据特定条件对字符串中的字符进行操作。今天，我们将探讨一个有趣的问题：只反转字符串中的字母字符，而非字母字符保持原位。这个问题看似简单，但蕴含着双指针算法的精髓。
目录
引言
问题描述
算法实现
算法解析
1. 双指针技术
2. 算法步骤
3. 边界条件处理
字符判断函数详解
算法优化
1. 使用标准库函数
2. 使用位运算加速
3. 添加内联优化
时间复杂度与空间复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)
变种问题
1. 只反转数字
2. 只反转元音字母
3. 保留特定模式
实际应用场景
测试用例设计
常见错误与注意事项
扩展：Unicode支持
总结
问题描述
给定一个字符串s，要求反转字符串中所有字母字符的位置，但保持非字母字符在原位。
示例 1：
text
输入：s = "ab-cd" 输出："dc-ba" 解释：字母'a'和'b'、'c'和'd'交换位置，连字符'-'保持原位
示例 2：
text
输入：s = "a-bC-dEf-ghIj" 输出："j-Ih-gfE-dCba"
示例 3：
text
输入：s = "Test1ng-Leet=code-Q!" 输出："Qedo1ct-eeLg=ntse-T!"
算法实现
cpp
class Solution { public: // 判断字符是否为字母 bool isLetter(char ch) { if(ch >= 'a' && ch <= 'z') return true; if(ch >= 'A' && ch <= 'Z') return true; return false; } // 只反转字符串中的字母 string reverseOnlyLetters(string s) { int left = 0, right = s.size() - 1; while(left < right) { // 从左向右找到第一个字母 while(left < right && !isLetter(s[left])) { left++; } // 从右向左找到第一个字母 while(left < right && !isLetter(s[right])) { right--; } // 交换两个字母 swap(s[left++], s[right--]); } return s; } };算法解析
1. 双指针技术
这是典型的双指针（对撞指针）技术：
left指针从字符串开头向右移动right指针从字符串末尾向左移动两个指针相向而行，直到相遇或交错
2. 算法步骤
text
初始状态：s = "a-bC-dEf-ghIj" left = 0, right = 12 第1轮： 跳过非字母：left指向0('a')，right指向12('j') 交换：s[0]和s[12]交换 → s = "j-bC-dEf-ghIa" left++ → 1, right-- → 11 第2轮： 跳过非字母：left指向2('b')，right指向10('h') 交换：s[2]和s[10]交换 → s = "j-hC-dEf-gbIa" left++ → 3, right-- → 9 第3轮： 跳过非字母：left指向4('C')，right指向8('g') 交换：s[4]和s[8]交换 → s = "j-hg-dEf-CbIa" left++ → 5, right-- → 7 第4轮： 跳过非字母：left指向6('E')，right指向6('E')（相同位置） 交换：s[6]和s[6]交换（实际不变） left++ → 7, right-- → 5 结束循环（left > right） 最终结果："j-Ih-gfE-dCba"3. 边界条件处理
空字符串或单字符字符串：直接返回原字符串
全是非字母字符：不会执行任何交换
全是字母字符：完全反转整个字符串
字符判断函数详解
cpp
bool isLetter(char ch) { // 方法1：使用字符范围判断（当前实现） if(ch >= 'a' && ch <= 'z') return true; if(ch >= 'A' && ch <= 'Z') return true; return false; // 方法2：使用C标准库函数 // return isalpha(ch); // 方法3：使用ASCII码特性 // return (ch >= 65 && ch <= 90) || (ch >= 97 && ch <= 122); }ASCII码相关知识：
大写字母：A-Z → 65-90
小写字母：a-z → 97-122
数字：0-9 → 48-57
算法优化
1. 使用标准库函数
cpp
bool isLetter(char ch) { return isalpha(ch); // C标准库函数，可识别本地化字符集 }2. 使用位运算加速
利用ASCII码的特性，字母的ASCII码与32（空格）进行或运算会得到小写形式：
cpp
bool isLetter(char ch) { // 转换为小写字母 char lower = ch | 32; // 判断是否为a-z return lower >= 'a' && lower <= 'z'; }3. 添加内联优化
cpp
class Solution { public: // 内联函数提高效率 inline bool isLetter(char ch) { return isalpha(ch); } string reverseOnlyLetters(string s) { // 算法主体不变 // ... } };时间复杂度与空间复杂度分析
时间复杂度：O(n)
每个字符最多被访问两次（一次由左指针，一次由右指针）
总操作次数不超过2n，其中n是字符串长度
空间复杂度：O(1)
只使用了常数个额外变量（left, right）
原地修改，不需要额外存储空间
变种问题
1. 只反转数字
cpp
string reverseOnlyDigits(string s) { int left = 0, right = s.size() - 1; while(left < right) { while(left < right && !isdigit(s[left])) left++; while(left < right && !isdigit(s[right])) right--; swap(s[left++], s[right--]); } return s; }2. 只反转元音字母
cpp
bool isVowel(char ch) { ch = tolower(ch); return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'; } string reverseOnlyVowels(string s) { int left = 0, right = s.size() - 1; while(left < right) { while(left < right && !isVowel(s[left])) left++; while(left < right && !isVowel(s[right])) right--; swap(s[left++], s[right--]); } return s; }3. 保留特定模式
cpp
// 反转字符串，但保持连字符分隔的单词内部顺序 // 例如："hello-world" -> "dlrow-olleh" string reverseWithSeparator(string s, char separator) { // 整体反转 reverse(s.begin(), s.end()); // 对每个分隔部分单独反转 int start = 0; for(int i = 0; i <= s.size(); i++) { if(i == s.size() || s[i] == separator) { reverse(s.begin() + start, s.begin() + i); start = i + 1; } } return s; }实际应用场景
文本处理：在编辑器中实现选择性反转
数据加密：对特定字符进行位置变换
字符串规范化：在保持格式的同时重新排列内容
代码混淆：对标识符中的字母进行反转
测试用例设计
全面的测试应该包括：
cpp
void test() { Solution sol; // 正常情况 assert(sol.reverseOnlyLetters("ab-cd") == "dc-ba"); assert(sol.reverseOnlyLetters("a-bC-dEf-ghIj") == "j-Ih-gfE-dCba"); assert(sol.reverseOnlyLetters("Test1ng-Leet=code-Q!") == "Qedo1ct-eeLg=ntse-T!"); // 边界情况 assert(sol.reverseOnlyLetters("") == ""); assert(sol.reverseOnlyLetters("a") == "a"); assert(sol.reverseOnlyLetters("123") == "123"); assert(sol.reverseOnlyLetters("!@#$") == "!@#$"); // 全字母情况 assert(sol.reverseOnlyLetters("abcdef") == "fedcba"); // 混合情况 assert(sol.reverseOnlyLetters("AaBbCc") == "cCbBaA"); assert(sol.reverseOnlyLetters("1a2b3c4d") == "1d2c3b4a"); }常见错误与注意事项
指针越界：确保while循环条件中包含
left < right字符编码：考虑不同的字符编码（ASCII vs Unicode）
性能考虑：避免在循环中重复计算
s.size()可读性：适当添加注释，特别是边界条件的处理
扩展：Unicode支持
对于Unicode字符，需要使用宽字符和相应的库函数：
cpp
#include <cwctype> // 用于宽字符判断 wstring reverseOnlyLettersUnicode(wstring s) { int left = 0, right = s.size() - 1; while(left < right) { while(left < right && !iswalpha(s[left])) left++; while(left < right && !iswalpha(s[right])) right--; swap(s[left++], s[right--]); } return s; }总结
这个字符串字母反转问题展示了双指针算法在字符串处理中的强大应用。通过这个算法，我们学习了：
双指针技巧：如何有效地同时从两端遍历和处理数据
字符分类：如何判断字符的类型（字母、数字、符号等）
原地修改：如何在不需要额外空间的情况下修改字符串
边界处理：如何正确处理各种边界情况
关键要点：
使用双指针从两端向中间遍历
跳过非目标字符，只处理符合条件的字符
确保指针不会越界
考虑各种边界情况和特殊输入
这个算法简单而高效，是面试中常见的题目，也是实际开发中处理字符串问题的有用工具。掌握这种模式，可以帮助我们解决许多类似的字符串操作问题。