LeetCode125 验证回文串 —— 字符串函数与 ASCII 码解析

一、题目核心概括题目要求给定字符串s判断它是否为回文串。判断规则分两步预处理大小写归一将所有大写字母 → 小写字母过滤字符移除非字母、非数字的字符空格、标点、符号回文判定预处理后的字符串正读反读完全一致则返回true关键细节字母和数字都属于字母数字字符alphanumeric空字符串视为回文串返回true只比较字母数字部分其他字符直接跳过三个典型示例输入预处理结果输出A man, a plan, a canal: Panamaamanaplanacanalpanamatruerace a carraceacarfalse 空串true二、算法思路双指针法这是最经典、最优雅的解法时间复杂度O(n)空间复杂度O(1)。text左指针 i → ← 右指针 j ↓ ↓ [ A m a n , a ... a n a m a ]算法流程初始化i 0左端j n - 1右端当i j循环跳过非法字符s[i]不是字母数字 →is[j]不是字母数字 →j--统一小写将两边字符都转小写比较若s[i] ! s[j]→ 立即返回false收缩指针ij--循环结束 → 返回true亮点无需额外分配空间边遍历边跳过一遍扫描即出结果。三、字符串相关函数全整理1. 判断类cctype头文件函数功能使用示例返回值isalnum(c)是否为字母或数字isalnum(A)非零真isalpha(c)是否为字母isalpha(5)0假isdigit(c)是否为数字isdigit(9)非零islower(c)是否为小写字母islower(a)非零isupper(c)是否为大写字母isupper(Z)非零isspace(c)是否为空白字符isspace( )非零ispunct(c)是否为标点符号ispunct(,)非零⚠️ 这些函数参数类型是int传入char时最好转成unsigned char避免负值导致越界LeetCode 一般没问题但工程中需注意。2. 转换类函数功能示例结果tolower(c)转小写tolower(A)atoupper(c)转大写toupper(a)A若传入的不是字母原样返回不会出错。3.std::string常用成员函数函数功能示例s.size()/s.length()返回长度abc.size()→ 3s.empty()是否为空.empty()→ trues[i]/s.at(i)访问第 i 个字符s[0]s.front()/s.back()首/尾字符s.back()s.substr(pos, len)取子串s.substr(1, 2)s.find(str)查找子串位置找不到返回nposs.push_back(c)尾部追加字符s.push_back(a)s.pop_back()删除尾部字符—s str拼接s abcs.clear()清空—s.reverse()需#include algorithm反转reverse(s.begin(), s.end())4. 大小写转换algorithmtransform(s.begin(), s.end(), s.begin(), ::tolower);四、ASCII 码核心知识1. 关键 ASCII 码表字符范围十进制十六进制说明0 ~ 948 ~ 570x30 ~ 0x39数字共 10 个A ~ Z65 ~ 900x41 ~ 0x5A大写字母共 26 个a ~ z97 ~ 1220x61 ~ 0x7A小写字母共 26 个 空格320x20—A与a差320x20关键数字2. 三大规律务必牢记规律一数字 大写字母 小写字母0(48) 9(57) A(65) Z(90) a(97) z(122)规律二大小写转换差值为 32char toLower(char c) { if (c A c Z) return c 32; // 大写 → 小写 return c; } char toUpper(char c) { if (c a c z) return c - 32; // 小写 → 大写 return c; }规律三字母、数字在 ASCII 表中是连续排列的所以判断是否为字母可以写成区间判断bool isLetter(char c) { return (c A c Z) || (c a c z); }3. 判断字符身份的推荐写法// 判断字母数字推荐直接用库函数 isalnum(c); // 手写版本 bool isAlphaNum(char c) { return (c 0 c 9) || (c A c Z) || (c a c z); }五、完整参考代码版本1推荐使用库函数#include cctype class Solution { public: bool isPalindrome(string s) { int i 0, j s.size() - 1; while (i j) { if (!isalnum(s[i])) { i; continue; } if (!isalnum(s[j])) { j--; continue; } if (tolower(s[i]) ! tolower(s[j])) return false; i; j--; } return true; } };版本2不用库函数class Solution { public: bool isPalindrome(string s) { int i 0, j s.size() - 1; while (i j) { // 跳过左侧非字母数字 bool leftValid (s[i] 0 s[i] 9) || (s[i] A s[i] Z) || (s[i] a s[i] z); if (!leftValid) { i; continue; } // 跳过右侧非字母数字 bool rightValid (s[j] 0 s[j] 9) || (s[j] A s[j] Z) || (s[j] a s[j] z); if (!rightValid) { j--; continue; } // 统一转小写 char cl (s[i] A s[i] Z) ? s[i] 32 : s[i]; char cr (s[j] A s[j] Z) ? s[j] 32 : s[j]; if (cl ! cr) return false; i; j--; } return true; } };版本3过滤 反转比较class Solution { public: bool isPalindrome(string s) { string t; // 准备一个新字符串 for (char c : s) { // 遍历原字符串 if (isalnum(c)) // 只保留字母和数字 t tolower(c); // 转小写后追加到 t } string r(t.rbegin(), t.rend()); // 反转 t 得到 r return t r; // 比较 t 和 r 是否相等 } };时间复杂度 O(n)空间复杂度 O(n)。思路直观但不如双指针省空间。