字符串题花样繁多，但高频考点集中在四块：反转系列、回文系列、子串匹配，以及匹配算法在工程中的落地方式。本篇沿这四条线梳理代表题型，重点讲清每种方法解决什么问题、代价是什么。

反转系列

思路：反转字符数组用首尾双指针原地交换；”反转单词顺序”则用两次反转——先整体反转，再逐个单词反转回来。

// 反转字符数组，原地、O(n) 时间、O(1) 空间
public void reverseString(char[] s) {
    for (int l = 0, r = s.length - 1; l < r; l++, r--) {
        char t = s[l]; s[l] = s[r]; s[r] = t;
    }
}

以 "the sky is blue" 为例：整体反转得到 "eulb si yks eht"，此时单词的先后顺序已经倒过来了，只是每个单词内部的字母也是反的；再对每个单词单独做一次反转，就得到 "blue is sky the"。这个”整体 + 局部”的两次反转套路还能迁移到”把数组循环右移 k 位”等题目上。

Java 里 String 不可变，无法原地修改，要先转成 char[] 操作再拼回来；循环里直接用 + 拼接字符串会反复复制，产生 O(n²) 的隐含成本，务必用 StringBuilder。

易错点：交换条件是 l < r 而不是 l <= r；输入句子含首尾或多重空格时，要先 trim 并压缩空格再处理，否则反转出的单词之间会夹带多余空白。

回文：判定与最长回文子串

判定用首尾双指针向中间收拢即可：跳过字母和数字之外的字符、统一转小写后比较，任一位置不等即非回文，时间 O(n)。

最长回文子串（LeetCode 5）有两种主流做法，值得对比理解：

  • 中心扩展：回文串一定关于某个中心对称。中心可以是某个字符（奇数长度）或相邻两字符之间（偶数长度），共 2n-1 种；从每个中心向两侧扩展直到两端字符不等，记录最长结果。时间 O(n²)、额外空间 O(1)，代码十几行，是面试的首选写法。
  • 动态规划：定义 dp[i][j] 表示子串 s[i..j] 是否为回文，转移方程为 dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]，按区间长度从小到大填表。时间同为 O(n²)，但空间要 O(n²)，常数也更大；好处是这张表可以复用，适合”统计回文子串个数”这类需要枚举所有区间的题。
public String longestPalindrome(String s) {
    int start = 0, max = 0;
    for (int i = 0; i < s.length(); i++) {
        int len = Math.max(expand(s, i, i), expand(s, i, i + 1));
        if (len > max) { max = len; start = i - (len - 1) / 2; }
    }
    return s.substring(start, start + max);
}

// 从中心 (l, r) 向两侧扩展，返回回文长度
private int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    return r - l - 1;
}

由 start = i - (len - 1) / 2 反推起点这一个公式同时覆盖了奇偶两种中心，值得记下来。

易错点：中心扩展必须同时枚举奇、偶两种中心，只枚举单字符中心会漏掉 "bb" 这类偶数回文；DP 版本的填表顺序要保证 dp[i+1][j-1] 先算出来，通常让 i 从大到小枚举；务必分清”子串”（必须连续）与”子序列”（可不连续），后者（如最长回文子序列）的转移方程完全不同，不能套用本题做法。

KMP：next 数组到底解决什么问题

先看朴素匹配的浪费在哪：主串指针 i 和模式串指针 j 逐位比较，失配时 i 回退到起点下一位、j 归零重头来过，最坏情况（形如 "aaaaab" 里找 "aaab"）达到 O(nm)。

KMP 的核心观察是：失配那一刻，模式串已匹配的前缀里可能藏着”既是最长前缀又是最长后缀”的一段，这段在主串里已经对上过了，没必要重新比。模式串可以直接向右滑动，让这段前后缀对齐，主串指针 i 全程不回退。

next 数组正是这个跳跃表：next[j] 表示模式串前 j 个字符中最长公共前后缀的长度，失配时 j 跳到 next[j] 继续比。预处理 O(m)、匹配 O(n)，合计 O(n+m)。面试通常不要求徒手推导 next 的构造细节，但要能讲清”利用已匹配信息、主串指针不回退”这层思想，以及它为什么把复杂度从乘积降到加和。

字符串匹配在工程中的应用

  • 编辑器与命令行的查找：短模式串、交互式场景下，很多实现选择 Boyer-Moore 族算法——从右往左比对，失配时按坏字符与好后缀规则大跨度右滑，实践中往往比 KMP 更快，GNU grep 就采用这类思路。
  • JDK 的 String.indexOf：实现是带剪枝的朴素匹配。短模式串下常数极小、缓存友好，说明理论复杂度最优不等于工程最优。
  • 多模式匹配：敏感词过滤、入侵检测系统（如 Snort）需要一次扫描命中成千上万个模式串，用的是 AC 自动机（KMP 思想在字典树上的推广）；Rabin-Karp 用滚动哈希给模式串算指纹，适合文档查重、抄袭检测这类”找相同片段”的场景。

小结

反转与回文判定考的是双指针基本功；最长回文子串优先用中心扩展，需要枚举所有区间时再用 DP；KMP 抓住”next 数组让主串指针不回退”的思想即可，不必陷进推导细节；工程选型先看模式串的数量和长度，再决定用朴素、Boyer-Moore 还是 AC 自动机。