系列文章目录
《JavaScript 基础与进阶笔记》（前期偏基础巩固与常见面试点，后续进入闭包、异步、工程化等进阶主题）
- 第 01 篇：数据类型与类型判断
- 第 02 篇：变量声明与作用域
- 第 03 篇：闭包与高阶函数
- 第 04 篇：函数工厂
- 第 05 篇：this 指向与绑定
- 第 06 篇：原型与原型链
- 第 07 篇：类与继承
- 第 08 篇：JS 执行机制与异步队列
- 第 09 篇：数组常用方法
- 第 10 篇：字符串算法（本文）
文章目录
- 系列文章目录
- 前言
- 一、预备：不可变与遍历方式
- 二、反转字符串
- 三、回文判断
- 四、最长公共子串（连续）
- 五、最长回文子串
- 六、KMP：思路与 `next` 数组
- 七、滑动窗口：无重复字符的最长子串
- 八、简易模板引擎
- 九、易混淆点归纳
- 十、思考与练习
- 总结
前言
字符串处理在面试与工程里同样高频：判断回文、求公共子串、模式匹配、以及把模板里的占位符替换成真实数据。许多题目依托双指针（头尾夹逼、快慢指针）或滑动窗口（维护区间性质），在此基础上再谈复杂度才算完整。本篇按「反转 → 回文 → 公共子串 / 最长回文子串 → KMP 思想 → 简易模板引擎」展开，与大纲「第二阶段：常用算法与手写题」第 10 节对齐；算法以 JavaScript 书写，必要时点出与 Unicode 相关的边界。
一、预备：不可变与遍历方式
- 字符串不可变：对字符串按下标赋值（在严格模式或一般赋值场景）不会改写原串，需通过切片拼接得到新串。
- 访问字符：
s[i]得到的是UTF-16 码元； emoji、部分汉字可能占两个码元，若题目涉及「按字符」而非「按码元」计数，需考虑[...s]、Array.from(s)或国际化 API（本篇例题以 ASCII / 基本多文种平面内的常规输入为主）。 - 工具方法：
slice、substring、split、replace、includes、indexOf等可与手写逻辑对照使用（详见第 9 篇思路），面试手写题仍建议练「双指针 + 自行比较」。
二、反转字符串
双指针：左l = 0、右r = n - 1，交换s[l]与s[r]，直至l >= r。字符串需先转成数组再交换，最后再join。
constreverseString=(str)=>{consta=[...str];letl=0;letr=a.length-1;while(l<r){[a[l],a[r]]=[a[r],a[l]];l++;r--;}returna.join("");};reverseString("hello");// "olleh"内置：[...str].reverse().join("")或按题意使用Array.from。时间复杂度O(n)，额外空间O(n)（存放字符数组）。
三、回文判断
定义：正读与反读相同（忽略大小写、仅看字母数字时常需先规范化）。
双指针：规范化后，从两端向中间比较；遇不相同即返回false。
constisPalindrome=(s)=>{constt=s.toLowerCase().replace(/[^a-z0-9]/g,"");letl=0;letr=t.length-1;while(l<r){if(t[l++]!==t[r--])returnfalse;}returntrue;};isPalindrome("A man, a plan, a canal: Panama");// true时间复杂度O(n)。若不要求过滤非字母数字，直接对原串双指针即可。
四、最长公共子串（连续）
与最长公共子序列（不必连续）不同，子串要求在主串中连续出现。
动态规划：设dp[i][j]表示以a[i-1]与b[j-1]结尾的最长公共子串长度；若a[i-1] === b[j-1]则dp[i][j] = dp[i-1][j-1] + 1，否则为0。扫描过程中记录最大值与结束位置即可还原子串。时间O(mn)，空间可压成O(min(m,n))的一维滚动（此处给出二维写法便于理解）。
constlongestCommonSubstring=(a,b)=>{constm=a.length;constn=b.length;letmaxLen=0;letend=0;constdp=Array.from({length:m+1},()=>newArray(n+1).fill(0));for(leti=1;i<=m;i++){for(letj=1;j<=n;j++){if(a[i-1]===b[j-1]){dp[i][j]=dp[i-1][j-1]+1;if(dp[i][j]>maxLen){maxLen=dp[i][j];end=i;}}}}returnmaxLen===0?"":a.slice(end-maxLen,end);};longestCommonSubstring("abcde","xbcdy");// "bcd"五、最长回文子串
中心扩展：枚举每个中心（奇数长度中心为一个字符，偶数长度中心为两个字符之间），向两侧扩展，记录最长区间。复杂度O(n²)，空间O(1)。
constlongestPalindrome=(s)=>{constexpand=(l,r)=>{while(l>=0&&r<s.length&&s[l]===s[r]){l--;r++;}returnr-l-1;};letstart=0;letmax=0;for(leti=0;i<s.length;i++){constlenOdd=expand(i,i);constlenEven=expand(i,i+1);constlen=Math.max(lenOdd,lenEven);if(len>max){start=i-Math.floor((len-1)/2);max=len;}}returns.slice(start,start+max);};longestPalindrome("babad");// "bab" 或 "aba"Manacher 算法可在线性时间内求解，篇幅所限这里不展开，面试问到再往「回文半径数组」方向准备即可。
六、KMP：思路与next数组
在文本text中找模式pattern，暴力做法是失配后text回溯，最坏O(nm)。KMP在模式串上预处理next（或pi）数组：失配时pattern内部已匹配的前后缀告诉我们pattern右移多少格，text指针不必回退，整体O(n + m)。
next[j]的常见定义：pattern[0..next[j]-1]既是pattern[0..j-1]的真前缀又是真后缀的最大长度。匹配时若text[i] !== pattern[j]，令j = next[j]重试；若j为 0仍失配则i++。
constbuildNext=(p)=>{constnext=[0];letj=0;for(leti=1;i<p.length;i++){while(j>0&&p[i]!==p[j])j=next[j-1];if(p[i]===p[j])j++;next[i]=j;}returnnext;};constkmpSearch=(text,pattern)=>{if(!pattern.length)return0;constnext=buildNext(pattern);letj=0;for(leti=0;i<text.length;i++){while(j>0&&text[i]!==pattern[j])j=next[j-1];if(text[i]===pattern[j])j++;if(j===pattern.length)returni-pattern.length+1;}return-1;};kmpSearch("ababcababa","aba");// 0不同资料对next下标与「右移」表述略有差异，手写时先在纸上画一轮失配会更稳。
七、滑动窗口：无重复字符的最长子串
滑窗：右边界r每次右移一格，用Map / Set记录当前窗口内字符及其位置；若新字符已存在且索引≥ l，则左边界l跳到重复字符右侧。维护r - l + 1的最大值。
constlengthOfLongestSubstring=(s)=>{constmap=newMap();letl=0;letans=0;for(letr=0;r<s.length;r++){constc=s[r];if(map.has(c)&&map.get(c)>=l)l=map.get(c)+1;map.set(c,r);ans=Math.max(ans,r-l+1);}returnans;};lengthOfLongestSubstring("abcabcbb");// 3 ("abc")时间O(n)，每个位置最多被左、右指针各扫一次。
八、简易模板引擎
将形如${name}或{{name}}的占位符替换为数据对象上的值，可用正则结合替换回调；缺失键时通常置空字符串或保留占位符（按产品约定）。
constrender=(tpl,data)=>tpl.replace(/\$\{(\w+)\}/g,(_,key)=>Object.prototype.hasOwnProperty.call(data,key)?String(data[key]):"",);consttpl="Hello, ${name}! Today is ${day}.";render(tpl,{name:"Tom",day:"Monday"});// "Hello, Tom! Today is Monday."若要防止XSS，应对输出做转义或在框架层统一处理，不可仅做字符串拼接。
九、易混淆点归纳
- 子串 vs 子序列：子串必须连续；子序列只保持相对顺序。DP 状态转移写法不同。
- 双指针既可用于反转、回文，也可配合排序数组；滑窗适合「区间满足某性质」的最值问题。
s[i]与 Unicode：按「用户可见字符」计数时，勿默认.length等于字符数。- KMP 与正则引擎：正则实现复杂得多；KMP 是确定有限状态下的经典教材模型。
- 复杂度口述：中心扩展回文O(n²)；公共子串 DPO(mn)；KMPO(n+m)；滑窗O(n)。
十、思考与练习
1.判断"0P"（零与大写 P）在「只保留字母数字并忽略大小写」的规则下是否为回文？
解析：规范化后为"0p"，首尾0与p不同，故为false。
2.为何最长公共子串 DP 中失配时dp[i][j] = 0，而最长公共子序列失配时往往继承max(dp[i-1][j], dp[i][j-1])？
解析：子串要求连续，一旦当前字符不相等，以当前位置结尾的公共连续段长度归零；子序列不要求连续，故可继承两侧已有长度。
3.无重复字符最长子串中，为何左边界要跳到map.get(c) + 1而不是只l++？
解析：重复字符可能出现在当前窗口左侧之外，若仅l++无法一次性剔除窗口内全部非法内容；用上次出现位置 + 1才能保证窗口内无重复。
总结
- 反转、回文多用双指针，注意规范化与 Unicode。
- 最长公共子串用DP或扩展理解；最长回文子串常用中心扩展 O(n²)。
- KMP通过
next避免文本回溯，复杂度O(n+m)。 - 滑动窗口解决「不重复最长子串」等区间问题。
- 模板替换可用正则
replace；线上需配合安全转义。
下一篇计划整理常见手写题合集（上）：深拷贝与浅拷贝、structuredClone、防抖与节流等，延续本阶段手写主线。
