字符串算法

系列文章目录《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];letl0;letra.length-1;while(lr){[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){constts.toLowerCase().replace(/[^a-z0-9]/g,);letl0;letrt.length-1;while(lr){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){constma.length;constnb.length;letmaxLen0;letend0;constdpArray.from({length:m1},()newArray(n1).fill(0));for(leti1;im;i){for(letj1;jn;j){if(a[i-1]b[j-1]){dp[i][j]dp[i-1][j-1]1;if(dp[i][j]maxLen){maxLendp[i][j];endi;}}}}returnmaxLen0?:a.slice(end-maxLen,end);};longestCommonSubstring(abcde,xbcdy);// bcd五、最长回文子串中心扩展枚举每个中心奇数长度中心为一个字符偶数长度中心为两个字符之间向两侧扩展记录最长区间。复杂度O(n²)空间O(1)。constlongestPalindrome(s){constexpand(l,r){while(l0rs.lengths[l]s[r]){l--;r;}returnr-l-1;};letstart0;letmax0;for(leti0;is.length;i){constlenOddexpand(i,i);constlenEvenexpand(i,i1);constlenMath.max(lenOdd,lenEven);if(lenmax){starti-Math.floor((len-1)/2);maxlen;}}returns.slice(start,startmax);};longestPalindrome(babad);// bab 或 abaManacher 算法可在线性时间内求解篇幅所限这里不展开面试问到再往「回文半径数组」方向准备即可。六、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];letj0;for(leti1;ip.length;i){while(j0p[i]!p[j])jnext[j-1];if(p[i]p[j])j;next[i]j;}returnnext;};constkmpSearch(text,pattern){if(!pattern.length)return0;constnextbuildNext(pattern);letj0;for(leti0;itext.length;i){while(j0text[i]!pattern[j])jnext[j-1];if(text[i]pattern[j])j;if(jpattern.length)returni-pattern.length1;}return-1;};kmpSearch(ababcababa,aba);// 0不同资料对next下标与「右移」表述略有差异手写时先在纸上画一轮失配会更稳。七、滑动窗口无重复字符的最长子串滑窗右边界r每次右移一格用Map / Set记录当前窗口内字符及其位置若新字符已存在且索引≥ l则左边界l跳到重复字符右侧。维护r - l 1的最大值。constlengthOfLongestSubstring(s){constmapnewMap();letl0;letans0;for(letr0;rs.length;r){constcs[r];if(map.has(c)map.get(c)l)lmap.get(c)1;map.set(c,r);ansMath.max(ans,r-l1);}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]):,);consttplHello, ${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(nm)滑窗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(nm)。滑动窗口解决「不重复最长子串」等区间问题。模板替换可用正则replace线上需配合安全转义。下一篇计划整理常见手写题合集上深拷贝与浅拷贝、structuredClone、防抖与节流等延续本阶段手写主线。