字符串

字符串与 JavaScript 的那些坑

算法视角下的字符串

对绝大多数算法题来说，字符串就是一个不可变的字符数组。 数组基础里那套东西直接搬过来：

  • 快慢指针 + 覆盖 → 原地去重、压缩
  • 左右指针对撞 → 回文判断、反转
  • 滑动窗口 → 最长无重复子串、异位词
  • 前缀和 → 区间内某字符出现几次

⭐ 所以这一章不重讲那些技巧，只讲字符串特有的东西： JavaScript 的几个坑、KMP 匹配、回文。

🚨 .length 数的不是字符

这是 JavaScript（以及 Java、C#）最容易踩的一个：

const s = 'ab👍cd';
s.length          // 6   ← 不是 5
[...s].length     // 5   ← 这才是「字符」数

原因是 JS 字符串底层是 UTF-16 码元序列。基本平面之外的字符（emoji、 部分生僻汉字）要用两个码元表示，这一对叫「代理对」。 .length 数的是码元，不是人眼看到的字符。

后果：split('').reverse().join('') 会把 emoji 拆坏

这是网上最流行的「反转字符串」写法，它对含 emoji 的串是错的：

const s = 'ab👍cd';

s.split('').reverse().join('')   // "dc👍 反了" → 乱码 💥
[...s].reverse().join('')        // "dc👍ba"  ✅

split('') 按码元切，把代理对的两半拆开、再倒过来拼 —— 高低位颠倒，渲染出来是两个「未知字符」方块。

⭐ 展开语法 [...s] 和 for...of 按码点迭代，不会拆坏代理对。 记这一条就够：要按「人看到的字符」处理，就用 [...s]，别用 split('')。

⚠️ 顺带：charCodeAt 返回码元，codePointAt 返回码点。 上面那个串里 s.charCodeAt(2) 是 55357（半个 emoji）， s.codePointAt(2) 是 128077（完整的 👍）。

📌 算法题的输入通常保证是 ASCII 或小写字母，这些坑不会触发。 但面试官问起来、或者写真实代码时，这是个能体现细致的点。

🚨 一条已经过时的性能建议

「循环里用 += 拼字符串是 O(n²)，要用数组 push + join」—— 这条建议在很多教程里还在流传。在现代 V8 上它已经不成立了。

⚠️ 别去记「哪个快几毫秒」 —— 这两个数完全被 JIT 预热支配，连快慢顺序都会翻转：

拼接 20 万次      冷启动     预热后取最小
s += 'x'          13.0 ms        1.7 ms
arr.push + join    7.3 ms        3.7 ms

🚨 冷启动时 += 慢一倍，预热后 += 反而快一倍。差别可以忽略，就这一句是稳的。

⭐ 真正要证的是「不是 O(n²)」，而这该看规模翻倍耗时怎么涨：

n = 1,000,000     34 ms
n = 2,000,000     88 ms    ×2.57
n = 4,000,000    185 ms    ×2.10
n = 8,000,000    396 ms    ×2.14

翻倍就是翻倍，不是翻四倍 —— O(n²) 该是 ×4。原因是 V8 用 rope（绳索） 表示拼接结果 —— a + b 不会真的复制出一个新串，只是建一个「左边是 a、右边是 b」的节点， 真正需要连续内存时才展平。

⚠️ 但别把这条反过来用：这是引擎实现，不是语言保证。 换个引擎、或者拼接后频繁做 charAt 之类的随机访问（会强制展平）， 结论可能不同。

📌 结论：算法题里怎么顺手怎么写，不必为了这条建议扭曲代码。 真遇到性能问题再测，别凭传说优化。

⚠️ sort() 默认按字符串排

这条严格说不是字符串的坑，但它是字符串行为泄漏到别处造成的：

[10, 9, 1].sort()                  // [1, 10, 9]   ← 不是 [1, 9, 10]
[10, 9, 1].sort((a, b) => a - b)   // [1, 9, 10]   ✅

Array.prototype.sort 不传比较函数时，把每个元素转成字符串再按码点比。 "10" < "9" 因为 '1' < '9'。

🚨 这个错在元素都是非负个位数时完全不出现 —— 0~9 的全排列跑了 20 万组， 一次都没暴露。所以 [3,1,2].sort() 结果是对的，看起来像「排序好像没生效」。

⚠️ 但「个位数」这个说法漏了负数。[-1, -2].sort() 就已经错了：

[-1, -2].sort()                  → [-1, -2]    ❌
[-1, -2].sort((a, b) => a - b)   → [-2, -1]    ✅

因为比的是 "-1" 和 "-2"，第二个字符 '1' < '2'，负号那一位一样 —— 数值越小的负数排在越后面。两个元素就够构成反例。

⚠️ 暴露率还不是单调的：

元素范围     0~9     0~20    0~100   0~1000
暴露率      0.0%    80.2%    30.7%    31.6%

0~20 是最凶的一档 —— 那里个位数和两位数混得最匀。 范围一大，多数元素位数相同，字符串序反而常常和数值序一致。 👉 所以「用大一点的随机数测一测」也未必抓得到，0~100 只有三成。

📌 排数字永远写比较函数。 这是 JS 里最高频的低级错误之一。

字符串比较与常用操作

'apple' < 'banana'   // true  —— 按码点逐位比，即字典序
'Z' < 'a'            // true  —— 大写字母码点更小，全排在小写前面

⚠️ 第二条的后果是大小写会压倒字母顺序。同样两个词，换个大小写结果就翻：

['banana', 'Apple'].sort()   → ['Apple', 'banana']    看着对（A 在 b 前）
['apple', 'Banana'].sort()   → ['Banana', 'apple']    🚨 B 排到了 a 前面

码点：'B' = 66    'Z' = 90    'a' = 97

👉 第一行碰巧和人的直觉一致，第二行就露馅了 —— 排序依据根本不是字母，是「先按大小写分两拨」。 要按人的习惯排用 localeCompare： ['apple','Banana'].sort((a, b) => a.localeCompare(b)) 得到 ['apple', 'Banana']。

子串操作的代价：slice / substring 在 V8 上对长串是 O(1) 的 （内部用 SlicedString 记录「原串 + 起止」，不复制）。

🚨 但**「1000 万字符的串上做 10 万次 slice(i, i+10) 只要 1 ms」证明不了这一点。** 切出来只有 10 个字符，就算老老实实复制也才 100 万次字符拷贝 —— 当然快。

⭐ 能证明「不复制」的实验是：固定切的次数，只改切出来多长。

1000 万字符的串，各做 1 万次 slice
  子串长度       10      100     1000    10000   100000   1000000
  耗时(ms)     0.10     0.05     0.05     0.05     0.05      0.31

👉 子串长度涨了 10 万倍，耗时几乎没动。这才是「没有复制」的证据。

⚠️ 而且有个门槛：V8 的 SlicedString 要求结果长度 ≥ 13（源码里的 kMinLength）， 短于这个数就退回真复制。所以会出现「切得越长反而越快」的怪现象：

20 万次 slice   长度 12 → 2.0 ms      长度 13 → 0.9 ms      长度 20 → 0.9 ms

📌 同样是引擎实现细节，别当成语言保证。但至少说明算法题里不用为了避开 slice 而写得很别扭。

下一步

字符串特有的两个大题型：

练习

勾选记录做过哪些，0 / 5 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。