专题 21字符串算法

21.1字符串题的四种武器

在动手写代码前，先把「这类题我该掏哪把刀」想清楚，能省下大量试错时间。字符串题翻来覆去就这四类套路，前两种你早就会了，后两种是本章新补的：

为什么回文和模拟要单列出来

回文问题有个特点：它天然「对称」，但对称的中心可能是字符，也可能是两个字符中间的空隙。这种「奇偶两种中心」的细节，用滑窗很难干净地表达，所以单独给一套「中心扩展」的打法。

模拟类题（比如两个字符串形式的大数相加）则反过来——它没有任何巧妙算法，考的就是你能不能把小学竖式一丝不苟地翻译成代码：末位对齐、逐位加、处理进位、处理长度不等。这类题「暴力就是最优解」，拼的是细心。

21.2最长回文子串：中心扩展（中等，力扣 5）

中等 核心：枚举 2n-1 个中心 · 奇偶统一

题意：给你一个字符串 s，找出其中的最长回文子串（回文 = 正读反读一样的串，如 "aba"、"bb"），返回它。 例：s = "babad" → 最长回文是 "bab"（或 "aba"，返回哪个都算对）；s = "cbbd" → "bb"。

思路推导

第一步，暴力。枚举所有子串（O(n²) 个），每个判断是不是回文（O(n)），总 O(n³)。太慢，但给了我们一个正确性的底线。

第二步，换个角度：从「中心」往外扩。任何一段回文，都围绕某个中心左右对称。比如 "aba" 以中间的 'b' 为中心，"bb" 以两个 'b' 中间的「空隙」为中心。 如果我们枚举每一个可能的中心，从它开始向两边比对，一旦左右字符不相等就停，那么从当前中心能扩出的最长回文就找到了。把每个中心的结果取最大，就是答案。

第三步，奇偶中心怎么统一。这是最容易漏的点：

• 长度为奇数的回文（如 "aba"），中心是一个字符；
• 长度为偶数的回文（如 "bb"），中心是两个字符之间的空隙。

如果只枚举「字符」当中心，会漏掉所有偶数长度回文。怎么办？把中心数从 n 个扩成 2n-1 个：把每个「字符」和每对「相邻字符的空隙」都当作中心。 代码上最干净的做法是写一个辅助函数 expand(left, right)，传两个起点：

中心 i（奇数长度）：expand(i, i)       // 左右从同一个字符出发
中心 i 与 i+1 之间（偶数）：expand(i, i+1)   // 左右从相邻两个字符出发

第四步，为什么不用 DP？最长回文子串也能用区间 DP：dp[i][j] 表示 s[i..j] 是否回文，根据 s[i]==s[j] 和 dp[i+1][j-1] 转移，时间 O(n²)、空间 O(n²)。 中心扩展同样是 O(n²) 时间，但空间只要 O(1)（只用了几个指针）。在「只求一个最长」的场景下，中心扩展又省空间又好写，所以优先用它；DP 版本的价值在于——它正是下一章 23.2 节「最长回文子序列」的铺垫，那里子序列不连续，中心扩展就不灵了。

参考代码

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) return s;   // 空或单字符，本身即回文
        int start = 0, maxLen = 1;                    // 记录最长回文的起点和长度
        for (int i = 0; i < s.length(); i++) {
            int len1 = expand(s, i, i);               // 以 i 为中心（奇数长度）
            int len2 = expand(s, i, i + 1);           // 以 i 与 i+1 间为中心（偶数长度）
            int len = Math.max(len1, len2);
            if (len > maxLen) {                        // 发现更长的，更新记录
                maxLen = len;
                start = i - (len - 1) / 2;            // 反推回文起点
            }
        }
        return s.substring(start, start + maxLen);    // 右开区间，含 start+maxLen 前一个
    }

    // 从 (left, right) 向两边扩，返回以之为中心的最长回文长度
    private int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length()
               && s.charAt(left) == s.charAt(right)) {
            left--;                                   // 左右相等，继续往外扩
            right++;
        }
        // 退出时 s[left]!=s[right] 或越界，回文长度为 (right-1)-(left+1)+1 = right-left-1
        return right - left - 1;
    }
}

复杂度

O(n²) 时间（2n-1 个中心，每个最多扩 n 步），O(1) 空间（只用了常数个指针）。这是面试里关于「最长回文子串」的标准写法。

21.3字符串相加：大数模拟（简单，力扣 415）

简单 核心：末位对齐 · 逐位加 · 进位

题意：给定两个非负整数的字符串 num1、num2（长度可能极大，大到 int 装不下），返回它们和的字符串（也不能用库函数直接转大数）。 例：num1 = "11", num2 = "123" → "134"；num1 = "0", num2 = "0" → "0"。

思路推导

第一步，明确为什么不能直接转。这是本题最关键的提醒：Integer.parseInt("12345678901234567890") 会直接溢出抛异常，因为 64 位 long 也才约 9×10¹⁸。题目给的「字符串」就是用来绕开数值类型上限的，所以必须按位模拟竖式加法。

第二步，回忆小学竖式。我们从两个数字的最右（个位）开始，一位一位往左加，每位产生一个「和」与一个「进位」：

    1 2 3
  +   1 1
  -------
    1 3 4     个位 3+1=4 无进位；十位 2+1=3；百位 1 落下

第三步，用双指针 + carry 翻译。设 i 指向 num1 末尾、j 指向 num2 末尾，carry 初始为 0。每一步：

• 取 digit1 = i>=0 ? num1[i]-'0' : 0（num1 用完了就补 0）；digit2 同理；
• sum = digit1 + digit2 + carry；
• 当前位结果 = sum % 10，新进位 carry = sum / 10；
• 两个指针都左移一位，直到两者都越界且 carry 也为 0。

第四步，注意结果顺序。我们从个位往高位算，得到的是「低位在前」的片段，最后要反转一下才是正常数字顺序。用 StringBuilder 拼接后 reverse() 即可。

参考代码

class Solution {
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1;          // 指向 num1 个位
        int j = num2.length() - 1;          // 指向 num2 个位
        int carry = 0;                       // 进位
        StringBuilder sb = new StringBuilder();
        while (i >= 0 || j >= 0 || carry != 0) {
            int d1 = i >= 0 ? num1.charAt(i) - '0' : 0;  // 用完补 0
            int d2 = j >= 0 ? num2.charAt(j) - '0' : 0;
            int sum = d1 + d2 + carry;
            sb.append(sum % 10);             // 当前位（低位先放）
            carry = sum / 10;                // 进位留给下一轮
            i--; j--;
        }
        return sb.reverse().toString();      // 反转成正常高位在前的顺序
    }
}

复杂度

O(max(n, m)) 时间（两个串各走一遍），O(max(n, m)) 空间（结果串长度）。这是「大数加法」的骨架，乘法、减法同一套路。

21.4反转字符串里的单词（中等，力扣 151）

中等 核心：trim + 从后往前拼 · 两次反转

题意：给你一个字符串 s，把其中单词的顺序反转，并去掉多余空格（单词间只留一个空格，首尾无空格）。 例：s = " the sky is blue " → "blue is sky the"。

思路推导

第一步，暴力直观法：分割再逆序。用 split(" +") 按空格切开，反转数组，再拼回去。能过，但面试官通常想看你会不会不依赖库函数、且 O(1) 额外空间地做。

第二步，从后往前直接拼（推荐）。既然要反转单词顺序，那就逆着读：用指针 i 从末尾往前扫，遇到单词就收集，遇到空格就跳过。收集一个单词后补一个空格，最后再 trim 掉末尾多余空格。这样一遍扫描就搞定，且只用 O(1) 额外变量（除了结果串）。

第三步，「原地 O(1) 空间」的两次反转技巧（提一嘴）。如果题目严格限制不能开新大数组，可以用「原地反转」三步法：

1. 先去掉多余空格（双指针把有效字符前移，压实）；
2. 整个字符串整体反转一遍（单词顺序被反过来，但每个单词内部也被反了）；
3. 再逐个单词内部反转回来。

例："the sky" → 压实 → 整体反转 "yks eht" → 单词内反转 "sky the"。两次反转互为抵消，巧妙地只用了几个指针变量就完成。本题我们用更直观的「从后往前拼」即可，但要知道这个技巧存在。

参考代码（从后往前拼，易读版）

class Solution {
    public String reverseWords(String s) {
        int i = s.length() - 1;             // 从末尾开始
        StringBuilder sb = new StringBuilder();
        while (i >= 0) {
            // ① 跳过尾部空格
            while (i >= 0 && s.charAt(i) == ' ') i--;
            if (i < 0) break;               // 全是空格，结束
            // ② 收集一个单词（从右往左读）
            int j = i;
            while (j >= 0 && s.charAt(j) != ' ') j--;
            // 此时 s[j+1 .. i] 是一个单词，按顺序加入结果
            sb.append(s.substring(j + 1, i + 1));
            sb.append(' ');                 // 单词间补一个空格
            i = j;                          // 继续往前
        }
        // 去掉最后一个多余空格（若存在）并返回
        return sb.length() == 0 ? "" : sb.substring(0, sb.length() - 1);
    }
}

复杂度

O(n) 时间（每个字符最多被访问一两次），O(n) 空间（StringBuilder 存结果）。如果要严格 O(1) 额外空间，则用上面的「两次反转」原地做法。

21.5KMP：next 数组怎么来的（中等，力扣 28，选学）

中等 核心：主串指针不回退 选学

题意：在字符串 haystack 中找出 needle 第一次出现的位置（返回下标），找不到返回 -1。 例：haystack = "aabaabaaf", needle = "aabaaf" → 出现在下标 3。

思路推导

第一步，朴素做法为什么慢。最直白：i 扫主串、j 扫模式串，一旦 haystack[i]!=needle[j] 就令 i 退回「本次起点 +1」、j 归零重来。最坏 O(n·m)。慢在哪？主串指针 i 反复回退。

第二步，核心思想：主串指针永不回退。既然匹配失败时已经比过了前面一段字符，那前面这段里藏着的信息能不能让我们不从头比？可以。关键观察：模式串自己前缀和后缀的重合，决定了「失败后能跳多远」。这就是 KMP 的全部动机。

第三步，next 数组 = 最长相等前后缀长度。对模式串的每个位置 i，定义 next[i] 为「needle[0..i] 这个前缀里，最长的、相等的前缀和后缀的长度」。 以前缀 ababc（假设模式 ababc... 的前 5 个字符）为例，逐位算：

模式:  a  b  a  b  c
下标:  0  1  2  3  4
next:  0  0  1  2  0

解释：
 i=0 'a'      : 单字符，前后缀无真重叠 → 0
 i=1 'ab'     : 前缀{a} 后缀{b} 不等 → 0
 i=2 'aba'    : 前缀{a} 后缀{a} 相等，长 1 → 1
 i=3 'abab'   : 前缀{ab} 后缀{ab} 相等，长 2 → 2
 i=4 'ababc'  : 前缀里没有以 c 结尾的等于后缀 c 的部分 → 0

第四步，怎么用 next 跳。匹配时 j 是模式串指针：若 haystack[i]==needle[j] 则两指针同进；一旦失配，不让 j 归零，而是 j = next[j-1]（利用已匹配部分的最长重合前缀），i 不动。这样主串 i 只增不减，整体 O(n+m)。

第五步，next 数组本身怎么求（自匹配）。用「模式串匹配自己」来填：len 表示当前已匹配的前后缀长度，i 从 1 走： 若 needle[i]==needle[len] 则 len++、next[i]=len；否则 len = next[len-1] 回退（len==0 时填 0）。

参考代码（完整版，第一次学只要求看懂思想）

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        int n = haystack.length(), m = needle.length();
        int[] next = buildNext(needle);     // 先算 next
        int j = 0;                           // 模式串指针
        for (int i = 0; i < n; i++) {
            // 失配就利用 next 回退 j（主串 i 不回退）
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;                         // 匹配上，j 前进
            }
            if (j == m) return i - m + 1;    // 整段匹配完，返回起点
        }
        return -1;
    }

    // 求 next 数组：next[i] = needle[0..i] 最长相等前后缀长度
    private int[] buildNext(String p) {
        int m = p.length();
        int[] next = new int[m];
        int len = 0;                         // 当前最长前后缀长度
        for (int i = 1; i < m; i++) {
            while (len > 0 && p.charAt(i) != p.charAt(len)) {
                len = next[len - 1];         // 回退到更短的可行前后缀
            }
            if (p.charAt(i) == p.charAt(len)) {
                len++;                       // 延长
            }
            next[i] = len;
        }
        return next;
    }
}

复杂度

建 next 数组 O(m)，匹配 O(n)，总 O(n+m) 时间，O(m) 空间。比朴素 O(n·m) 在长串上快非常多。

21.6Manacher 速览（概念，选学）

选学 核心：线性求最长回文

它解决什么：和 21.2 节同一个问题——求最长回文子串，但中心扩展是 O(n²)，Manacher 把它压到 O(n)。当你面对超长字符串（10⁵ 级）时，O(n²) 直接超时，才需要它。

两个关键直觉

① 用 '#' 统一奇偶。前面说过奇偶中心麻烦。Manacher 的预处理是：在原串每个字符之间和首尾都插入一个不会出现的字符（如 '#'）。 "aba" 变成 "#a#b#a#"，无论原来奇偶，处理后的回文一定以 '#' 为中心、长度必为奇数，中心数从 2n-1 简化成 n+1 个统一处理。

② 利用已算回文的「镜像」避免重复扩。这是精髓。维护一个已经到达的最右边界 R 及其对应的中心 C。当处理新中心 i 时：

• 若 i 在 R 内，则其关于 C 的镜像点 i' 的回文半径「至少」可以借用——不用从 1 重新开始扩，直接以镜像半径和「到右边界的距离」的较小值为起点继续扩；
• 扩完后若越过 R，更新 C=i、R=新右界。

因为每次扩都让 R 单调右移、且借用镜像省掉了内部重复扩展，总步数线性。

21.7本专题常见坑

21.8自测题