第87章 检查回文
案例87:检查回文——递归与双指针实现
题目:判断一个字符串是否为回文(正读、倒读相同),忽略大小写和非字母数字字符。
设计思路
先过滤字符串为纯字母数字并统一小写,再通过双指针从两端向中间比较字符。若所有对应字符相等则为回文,否则提前返回false。同时提供递归版本作为对比,强化对索引边界的控制。
核心代码
// 清理字符串:保留字母数字,转小写
function clean(s: string): string {
return s.toLowerCase().replace(/[^a-z0-9]/g, '');
}
// 双指针迭代
function isPalindrome(s: string): boolean {
const str = clean(s);
let left = 0, right = str.length - 1;
while (left < right) {
if (str[left] !== str[right]) return false;
left++;
right--;
}
return true;
}
// 递归版本
function isPalindromeRec(s: string, l = 0, r = s.length - 1): boolean {
if (l >= r) return true;
return s[l] === s[r] && isPalindromeRec(s, l + 1, r - 1);
}
// 测试
const cases = ['A man, a plan, a canal: Panama', 'race a car', '😊a😊'];
for (const c of cases) {
console.log(`"${c}" => `, isPalindrome(c));
}
console.log('递归检查 "abcba":', isPalindromeRec(clean('abcba')));
运行结果
正确输出:
"A man, a plan, a canal: Panama" => true
"race a car" => false
"😊a😊" => true(仅字母数字,忽略emoji)
递归检查 "abcba": true
"A man, a plan, a canal: Panama" => true
"race a car" => false
"😊a😊" => true(仅字母数字,忽略emoji)
递归检查 "abcba": true
测试建议
可用 ts-node 或 deno run 执行。建议增加空字符串(应为true)、全符号 "!!!"(应为true)等边界用例。
提示:
replace(/[^a-z0-9]/g,'') 会删除所有非字母数字字符,但会丢失Unicode字母(如中文、日文),若要支持多语言可改用 s.normalize('NFD').replace(/[\u0300-\u036f]/g,'') 等复杂方案。注意:递归版本不会自动清理字符串,必须先调用
clean() 再传入递归函数,否则"abc, cba"这类带符号字符串会错误返回false。成功要点:双指针时间复杂度O(n)、空间O(1);递归版本简洁但栈深受字符串长度限制,长文本建议用迭代法。
注意事项
1. 忽略大小写务必统一转小写;2. 使用while (left < right)避免奇偶长度误判;3. emoji等非字母数字字符会被过滤,如需保留需调整正则。