手撕字符串算法：反转、回文、验证回文 Ⅱ 完整拆解

文章目录一、反转字符串1.1 问题引入1.2 解法split → reverse → join1.3 深入原理JS 的包装类机制1.4 补充手写 reverse不用 API二、判断一个字符串是否是回文字符串2.1 什么是回文串2.2 解法一API 流简单直观2.3 解法二双指针更优解三、回文字符串的衍生问题3.1 问题描述3.2 核心思路贪心 双指针 分支验证3.3 完整代码实现3.4 易错点分析重要3.5 复杂度分析四、全文总结五、核心知识点复盘六、常见问题 / 避坑指南字符串是算法面试中的高频考点看似简单实则暗藏许多细节。本文从反转字符串出发深入到回文判断及其衍生变体穿插 JS 底层原理帮你一举拿下字符串相关面试题。一、反转字符串1.1 问题引入在 JavaScript 中字符串是不可变immutable的简单数据类型。一个常见面试题是给定一个字符串abc如何将其反转为cba新手可能会直觉地写出str.reverse()但字符串原型上根本没有reverse方法——那是数组才有的 API。1.2 解法split → reverse → join最经典的三段式解法conststrabc;// 1. split() → 将字符串打散为字符数组 [a, b, c]// 2. reverse() → 反转数组 [c, b, a]// 3. join() → 将数组重新拼接为字符串 cbaconstreversedstr.split().reverse().join();console.log(reversed);// cba思路解析步骤方法输入输出拆分split()abc[a, b, c]反转reverse()[a, b, c][c, b, a]合并join()[c, b, a]cba关键点split()用空字符串分割能将每个字符拆成独立数组元素。如果写成split()不传参会返回[abc]后续反转就失效了。1.3 深入原理JS 的包装类机制这里有一个值得追问的面试点letstrabc;// 简单数据类型console.log(str.length);// 3 — 简单类型为什么能访问属性str明明是简单数据类型存在栈内存按理说不应该有属性。但 JS 为了统一面向对象的编程体验在底层做了包装str.length 访问流程 1. JS 引擎临时 new String(str) → 将简单类型包装为 String 对象 2. 返回 String 实例的 .length 属性 3. 自动销毁临时对象str 恢复为简单类型这个过程被称为包装类Wrapper Class像灰姑娘的玻璃鞋——到点就消失。同样的机制也适用于Number和Boolean。可以用Object.prototype.toString来验证// 简单类型Object.prototype.toString.call(abc);// [object String]Object.prototype.toString.call(123);// [object Number]Object.prototype.toString.call(true);// [object Boolean]// 引用类型Object.prototype.toString.call([1,2,3]);// [object Array]Object.prototype.toString.call({a:1});// [object Object]核心知识点Object.prototype.toString.call()是 JS 中精确判断数据类型的终极武器比typeof和instanceof更可靠。它利用的是JS 一切皆是对象都继承自Object而toString方法能返回内部的[[Class]]属性从而区分不同子类型。1.4 补充手写 reverse不用 API如果面试官追问不借助数组 API 怎么反转用双指针functionreverseString(str){constarrstr.split();// 字符串不可变先转数组letleft0;letrightarr.length-1;while(leftright){// 交换左右字符[arr[left],arr[right]][arr[right],arr[left]];left;right--;}returnarr.join();}console.log(reverseString(abc));// cba二、判断一个字符串是否是回文字符串2.1 什么是回文串回文串Palindrome正着读和反着读完全一样的字符串。例如yessey从左到右和从右到左都是y-e-s-s-e-y。2.2 解法一API 流简单直观利用第一节的反转技巧一行搞定functionisPalindrome(str){returnstrstr.split().reverse().join();}console.log(isPalindrome(yessey));// trueconsole.log(isPalindrome(hello));// false时间复杂度O(n)空间复杂度O(n)反转时创建了新字符串。2.3 解法二双指针更优解不需要额外空间左右各一个指针向中间靠拢functionisPalindrome(str){constlenstr.length;for(leti0;ilen/2;i){// 左指针 i右指针 len - 1 - iif(str[i]!str[len-1-i]){returnfalse;// 发现不对称直接返回 false}}returntrue;// 完整遍历完是对称的}console.log(isPalindrome(yessey));// trueconsole.log(isPalindrome(hello));// false思路图解yessey ↑ ↑ i len-1-i 第1轮: y y ✅ → i 第2轮: e e ✅ → i 第3轮: s s ✅ → i (i3, len/23, 循环结束) 返回 true面试重点双指针只需遍历一半len/2时间 O(n)空间 O(1)是面试官更想看到的解法。API 法虽然简洁但创建了新数组和新字符串空间开销更大。三、回文字符串的衍生问题3.1 问题描述LeetCode 680. 验证回文字符串 Ⅱ给定一个非空字符串s最多删除一个字符。判断是否能成为回文字符串。示例1: aba → true本身就是回文 示例2: abca → true删除 b 或 c 后得到 aca 或 aba 示例3: abc → false删一个不够3.2 核心思路贪心 双指针 分支验证关键洞察先用双指针从两端向中间走遇到不相等的字符时停下此时有两个候选方案跳过左边 OR 跳过右边分别验证跳过后的子串是否为回文任意一个验证通过即返回 truea b c a ↑ ↑ L R 第1轮: a a ✅ → L, R-- 第2轮: b ! c ❌ → 停下分支验证 方案A: 跳过左边 → 验证 s[L1 ... R] ca → 不是回文 方案B: 跳过右边 → 验证 s[L ... R-1] bc → 不是回文 结果: false删一个不够a b c b a ↑ ↑ L R 完整走完 while → 本身就是回文 → true3.3 完整代码实现/** * 验证回文字符串 Ⅱ —— 最多删除一个字符 * param {string} s * return {boolean} */functionvalidPalindrome(s){constlens.length;letleft0;letrightlen-1;// 第一阶段双指针向中间收缩直到遇到不等字符while(leftrights[left]s[right]){left;right--;}// 如果 left right说明完整走完本身就是回文if(leftright){returntrue;}// 第二阶段分支验证// 方案A跳过左边字符验证 s[left1 ... right]// 方案B跳过右边字符验证 s[left ... right-1]returnisPalindrome(s,left1,right)||isPalindrome(s,left,right-1);}/** * 辅助函数验证 s[st...ed] 是否为回文闭区间 * param {string} s * param {number} st - 起始索引 * param {number} ed - 结束索引 * return {boolean} */functionisPalindrome(s,st,ed){while(sted){if(s[st]!s[ed]){returnfalse;}st;ed--;}returntrue;}// 测试用例console.log(validPalindrome(aba));// true — 本身就是回文console.log(validPalindrome(abca));// true — 删 b 或删 cconsole.log(validPalindrome(abc));// false — 删一个不够console.log(validPalindrome(deeee));// true — 删第一个 dconsole.log(validPalindrome(eeeed));// true — 删最后一个 d3.4 易错点分析重要易错点 1左右指针收缩逻辑要清晰// ❌ 错误写法条件判断写反while(leftrights[left]!s[right]){...}// ✅ 正确写法相等时收缩不等时停下while(leftrights[left]s[right]){left;right--;}易错点 2分支验证别忘了本身是回文的情况// aba 这样的字符串while 循环会完整走完// left1, right1 → left right → 直接返回 true// 如果不加这个判断就会错误地进入分支验证易错点 3辅助isPalindrome用闭区间而非开区间// ✅ 闭区间 [st, ed]更符合直觉isPalindrome(s,left1,right)// 跳过左边isPalindrome(s,left,right-1)// 跳过右边// ❌ 如果用开区间容易搞混边界3.5 复杂度分析指标值说明时间复杂度O(n)最坏情况两次遍历主循环 一次 isPalindrome空间复杂度O(1)只用了几个指针变量无额外数组四、全文总结本文从一道看似简单的反转字符串切入串联了三个层次的知识点API 层面split → reverse → join三段式反转掌握字符串与数组的转换技巧原理层面JS 包装类机制——简单类型为何能像对象一样调用属性Object.prototype.toString.call()精确类型判断算法层面回文判断的双指针解法以及最多删一个字符的贪心 分支验证思路五、核心知识点复盘知识点要点字符串反转字符串不可变借助数组split→reverse→join包装类简单类型访问属性时JS 临时new String()再销毁类型判断Object.prototype.toString.call()是判断类型的终极方法回文判断双指针向中间收缩比较对称字符时间 O(n) 空间 O(1)回文 Ⅱ遇到不等时分支验证跳过左或跳过右短路求值六、常见问题 / 避坑指南Q1为什么不用str.reverse()JS 字符串原型上没有reverse方法。字符串是不可变的reverse是数组的方法。先split转数组再操作。Q2split()和split()有什么区别split()按每个字符拆分split()不传参返回整个字符串作为单元素数组[abc]反转后还是自己达不到效果。字符串算法万变不离其宗核心是对对称性的理解和双指针的灵活运用。掌握文中这三道题的思路演变面试中的字符串问题基本都能迎刃而解。