【C++】字符串中的字母反转算法详解

引言在处理字符串时我们经常需要根据特定条件对字符串中的字符进行操作。今天我们将探讨一个有趣的问题只反转字符串中的字母字符而非字母字符保持原位。这个问题看似简单但蕴含着双指针算法的精髓。目录引言问题描述算法实现算法解析1. 双指针技术2. 算法步骤3. 边界条件处理字符判断函数详解算法优化1. 使用标准库函数2. 使用位运算加速3. 添加内联优化时间复杂度与空间复杂度分析时间复杂度O(n)空间复杂度O(1)变种问题1. 只反转数字2. 只反转元音字母3. 保留特定模式实际应用场景测试用例设计常见错误与注意事项扩展Unicode支持总结问题描述给定一个字符串s要求反转字符串中所有字母字符的位置但保持非字母字符在原位。示例 1text输入s ab-cd 输出dc-ba 解释字母a和b、c和d交换位置连字符-保持原位示例 2text输入s a-bC-dEf-ghIj 输出j-Ih-gfE-dCba示例 3text输入s Test1ng-Leetcode-Q! 输出Qedo1ct-eeLgntse-T!算法实现cppclass 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-dCba3. 边界条件处理空字符串或单字符字符串直接返回原字符串全是非字母字符不会执行任何交换全是字母字符完全反转整个字符串字符判断函数详解cppbool 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. 使用标准库函数cppbool isLetter(char ch) { return isalpha(ch); // C标准库函数可识别本地化字符集 }2. 使用位运算加速利用ASCII码的特性字母的ASCII码与32空格进行或运算会得到小写形式cppbool isLetter(char ch) { // 转换为小写字母 char lower ch | 32; // 判断是否为a-z return lower a lower z; }3. 添加内联优化cppclass Solution { public: // 内联函数提高效率 inline bool isLetter(char ch) { return isalpha(ch); } string reverseOnlyLetters(string s) { // 算法主体不变 // ... } };时间复杂度与空间复杂度分析时间复杂度O(n)每个字符最多被访问两次一次由左指针一次由右指针总操作次数不超过2n其中n是字符串长度空间复杂度O(1)只使用了常数个额外变量left, right原地修改不需要额外存储空间变种问题1. 只反转数字cppstring 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. 只反转元音字母cppbool 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; }实际应用场景文本处理在编辑器中实现选择性反转数据加密对特定字符进行位置变换字符串规范化在保持格式的同时重新排列内容代码混淆对标识符中的字母进行反转测试用例设计全面的测试应该包括cppvoid 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-Leetcode-Q!) Qedo1ct-eeLgntse-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; }总结这个字符串字母反转问题展示了双指针算法在字符串处理中的强大应用。通过这个算法我们学习了双指针技巧如何有效地同时从两端遍历和处理数据字符分类如何判断字符的类型字母、数字、符号等原地修改如何在不需要额外空间的情况下修改字符串边界处理如何正确处理各种边界情况关键要点使用双指针从两端向中间遍历跳过非目标字符只处理符合条件的字符确保指针不会越界考虑各种边界情况和特殊输入这个算法简单而高效是面试中常见的题目也是实际开发中处理字符串问题的有用工具。掌握这种模式可以帮助我们解决许多类似的字符串操作问题。