系列文章目录

《JavaScript 基础与进阶笔记》（前期偏基础巩固与常见面试点，后续进入闭包、异步、工程化等进阶主题）

• 第 01 篇：数据类型与类型判断
• 第 02 篇：变量声明与作用域
• 第 03 篇：闭包与高阶函数
• 第 04 篇：函数工厂
• 第 05 篇：this 指向与绑定
• 第 06 篇：原型与原型链
• 第 07 篇：类与继承
• 第 08 篇：JS 执行机制与异步队列
• 第 09 篇：数组常用方法
• 第 10 篇：字符串算法（本文）

---

---

前言

字符串处理在面试与工程里同样高频：判断回文、求公共子串、模式匹配、以及把模板里的占位符替换成真实数据。许多题目依托双指针（头尾夹逼、快慢指针）或滑动窗口（维护区间性质），在此基础上再谈复杂度才算完整。本篇按「反转 → 回文 → 公共子串 / 最长回文子串 → KMP 思想 → 简易模板引擎」展开，与大纲「第二阶段：常用算法与手写题」第 10 节对齐；算法以 JavaScript 书写，必要时点出与 Unicode 相关的边界。

---

一、预备：不可变与遍历方式

1. 字符串不可变：对字符串按下标赋值（在严格模式或一般赋值场景）不会改写原串，需通过切片拼接得到新串。
2. 访问字符：s[i] 得到的是 UTF-16 码元； emoji、部分汉字可能占两个码元，若题目涉及「按字符」而非「按码元」计数，需考虑 [...s]、Array.from(s) 或国际化 API（本篇例题以 ASCII / 基本多文种平面内的常规输入为主）。
3. 工具方法：slice、substring、split、replace、includes、indexOf 等可与手写逻辑对照使用（详见第 9 篇思路），面试手写题仍建议练「双指针 + 自行比较」。

---

二、反转字符串

双指针：左 l = 0、右 r = n - 1，交换 s[l] 与 s[r]，直至 l >= r。字符串需先转成数组再交换，最后再 join。

const reverseString = (str) => {
  const a = [...str];
  let l = 0;
  let r = a.length - 1;
  while (l < r) {
    [a[l], a[r]] = [a[r], a[l]];
    l++;
    r--;
  }
  return a.join("");
};

reverseString("hello"); // "olleh"

内置：[...str].reverse().join("") 或按题意使用 Array.from。时间复杂度 O(n)，额外空间 O(n)（存放字符数组）。

---

三、回文判断

定义：正读与反读相同（忽略大小写、仅看字母数字时常需先规范化）。

双指针：规范化后，从两端向中间比较；遇不相同即返回 false。

const isPalindrome = (s) => {
  const t = s.toLowerCase().replace(/[^a-z0-9]/g, "");
  let l = 0;
  let r = t.length - 1;
  while (l < r) {
    if (t[l++] !== t[r--]) return false;
  }
  return true;
};

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)) 的一维滚动（此处给出二维写法便于理解）。

const longestCommonSubstring = (a, b) => {
  const m = a.length;
  const n = b.length;
  let maxLen = 0;
  let end = 0;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 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;
        }
      }
    }
  }
  return maxLen === 0 ? "" : a.slice(end - maxLen, end);
};

longestCommonSubstring("abcde", "xbcdy"); // "bcd"

---

五、最长回文子串

中心扩展：枚举每个中心（奇数长度中心为一个字符，偶数长度中心为两个字符之间），向两侧扩展，记录最长区间。复杂度 O(n²)，空间 O(1)。

const longestPalindrome = (s) => {
  const expand = (l, r) => {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      l--;
      r++;
    }
    return r - l - 1;
  };
  let start = 0;
  let max = 0;
  for (let i = 0; i < s.length; i++) {
    const lenOdd = expand(i, i);
    const lenEven = expand(i, i + 1);
    const len = Math.max(lenOdd, lenEven);
    if (len > max) {
      start = i - Math.floor((len - 1) / 2);
      max = len;
    }
  }
  return s.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++。

const buildNext = (p) => {
  const next = [0];
  let j = 0;
  for (let i = 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;
  }
  return next;
};

const kmpSearch = (text, pattern) => {
  if (!pattern.length) return 0;
  const next = buildNext(pattern);
  let j = 0;
  for (let i = 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) return i - pattern.length + 1;
  }
  return -1;
};

kmpSearch("ababcababa", "aba"); // 0

不同资料对 next 下标与「右移」表述略有差异，手写时先在纸上画一轮失配会更稳。

---

七、滑动窗口：无重复字符的最长子串

滑窗：右边界 r 每次右移一格，用 Map / Set 记录当前窗口内字符及其位置；若新字符已存在且索引 ≥ l，则左边界 l 跳到重复字符右侧。维护 r - l + 1 的最大值。

const lengthOfLongestSubstring = (s) => {
  const map = new Map();
  let l = 0;
  let ans = 0;
  for (let r = 0; r < s.length; r++) {
    const c = 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);
  }
  return ans;
};

lengthOfLongestSubstring("abcabcbb"); // 3 ("abc")

时间 O(n)，每个位置最多被左、右指针各扫一次。

---

八、简易模板引擎

将形如 ${name} 或 {{name}} 的占位符替换为数据对象上的值，可用正则结合替换回调；缺失键时通常置空字符串或保留占位符（按产品约定）。

const render = (tpl, data) =>
  tpl.replace(/\$\{(\w+)\}/g, (_, key) =>
    Object.prototype.hasOwnProperty.call(data, key) ? String(data[key]) : "",
  );

const tpl = "Hello, ${name}! Today is ${day}.";
render(tpl, { name: "Tom", day: "Monday" });
// "Hello, Tom! Today is Monday."

若要防止 XSS，应对输出做转义或在框架层统一处理，不可仅做字符串拼接。

---

九、易混淆点归纳

1. 子串 vs 子序列：子串必须连续；子序列只保持相对顺序。DP 状态转移写法不同。
2. 双指针既可用于反转、回文，也可配合排序数组；滑窗适合「区间满足某性质」的最值问题。
3. s[i] 与 Unicode：按「用户可见字符」计数时，勿默认 .length 等于字符数。
4. KMP 与正则引擎：正则实现复杂得多；KMP 是确定有限状态下的经典教材模型。
5. 复杂度口述：中心扩展回文 O(n²)；公共子串 DP O(mn)；KMP O(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、防抖与节流等，延续本阶段手写主线。