字符串
2026/4/10大约 14 分钟常用算法题字符串
本章题海战术
字符串
📌 字符串算法考点体系图
🔥 高频题型 + 核心代码（Java 版）
💡 题型 1：反转字符串（双指针法）
- 核心思路：左右指针指向首尾，交换字符后向中间收缩，直到指针相遇
- 核心代码：
// 时间O(n) 空间O(1) 原地反转
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while (left < right) {
// 异或交换，省去临时变量
s[left] ^= s[right];
s[right] ^= s[left];
s[left] ^= s[right];
left++;
right--;
}
}- 技术亮点：异或运算实现无临时变量交换；
left < right边界条件天然兼容奇偶长度字符串。
💡 题型 2：无重复字符的最长子串（滑动窗口）
- 核心思路：滑动窗口 + 哈希表记录字符最后出现位置，右指针持续右移，遇重复字符时左指针直接跳到重复位置的下一位
- 核心代码：
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int maxLen = 0;
int left = 0; // 滑动窗口左边界
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (map.containsKey(c)) {
// 关键：左边界只右移不回退
left = Math.max(left, map.get(c) + 1);
}
map.put(c, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}- 技术亮点：一次遍历完成，时间复杂度 O (n)；
Math.max处理重复字符在窗口外的边界场景；纯小写字母场景可替换为数组进一步提速。
💡 题型 3：最长回文子串（中心扩散法）
- 核心思路：回文串分奇数 / 偶数两种中心，遍历每个位置作为中心向两边扩散，记录最长长度
- 核心代码：
public String longestPalindrome(String s) {
if (s.length() < 2) return s;
int start = 0, maxLen = 1;
for (int i = 0; i < s.length(); i++) {
int oddLen = expand(s, i, i); // 奇数长度中心
int evenLen = expand(s, i, i + 1); // 偶数长度中心
int curLen = Math.max(oddLen, evenLen);
if (curLen > maxLen) {
maxLen = curLen;
start = i - (curLen - 1) / 2; // 精准计算起始下标
}
}
return s.substring(start, start + maxLen);
}
// 中心扩散辅助方法
private int expand(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}- 技术亮点：统一处理奇偶长度回文，代码简洁；时间 O (n²)、空间 O (1)，比动态规划空间更优。
💡 题型 4：KMP 字符串匹配算法
- 核心思路：先构建 next 数组（最长相等前后缀），匹配时文本串指针永不回溯，仅回退模式串指针
- 核心代码：
// 返回模式串p在文本串s中第一次出现的下标
public int strStr(String s, String p) {
if (p.isEmpty()) return 0;
int[] next = buildNext(p);
int i = 0; // 文本串指针
int j = 0; // 模式串指针
while (i < s.length() && j < p.length()) {
if (j == -1 || s.charAt(i) == p.charAt(j)) {
i++;
j++;
} else {
j = next[j]; // 模式串按next数组回退
}
}
return j == p.length() ? i - j : -1;
}
// 构建next数组
private int[] buildNext(String p) {
int[] next = new int[p.length()];
next[0] = -1; // 哨兵位，统一边界逻辑
int i = 0, j = -1;
while (i < p.length() - 1) {
if (j == -1 || p.charAt(i) == p.charAt(j)) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
return next;
}- 技术亮点：时间复杂度 O (n+m)，远优于暴力匹配的 O (n*m)；利用已匹配信息避免重复比较；哨兵位
next[0]=-1简化边界判断。
💡 题型 5：有效的字母异位词（哈希计数）
- 核心思路：小写字母用长度 26 的数组计数，s 字符 + 1、t 字符 - 1，最终校验数组是否全 0
- 核心代码：
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;
for (char c : t.toCharArray()) count[c - 'a']--;
for (int num : count) {
if (num != 0) return false;
}
return true;
}- 技术亮点：数组替代 HashMap，常数级访问性能更优；固定大小数组，空间复杂度 O (1)。
⚠️ 技术难点与解决方案
| 技术难点 | 解决方案 |
|---|---|
| 边界条件复杂（空串、单字符、下标越界） | 开头先做空串 / 长度校验；循环严格控制下标范围；指针移动后先判断再访问字符 |
| 滑动窗口左边界错误回退 | 遇到重复字符时，用Math.max(left, 重复位置+1)保证左边界只右移不回退 |
| KMP next 数组逻辑难理解 | 记住核心定义：next [j] 表示 j 位置前子串的最长相等前后缀长度；用 - 1 作为哨兵统一边界 |
| 回文串奇偶长度处理混乱 | 中心扩散法同时处理单中心（奇数）和双中心（偶数）；动态规划统一状态转移 |
| Unicode / 中文等特殊字符场景 | Java 用codePointAt替代charAt；用 HashMap 替代固定长度计数数组 |
| 大数据量下性能损耗 | 优先用数组代替哈希表；避免频繁调用substring，用下标记录起止位置 |
📚 LeetCode 高频考题清单
| 分类 | 题号 | 题目名称 | 难度 | 核心解法 |
|---|---|---|---|---|
| 双指针 | 344 | 反转字符串 | 简单 | 左右双指针交换 |
| 双指针 | 541 | 反转字符串 II | 简单 | 按步长分段反转 |
| 双指针 | 151 | 翻转字符串里的单词 | 中等 | 双指针 + 倒序遍历 |
| 滑动窗口 | 3 | 无重复字符的最长子串 | 中等 | 滑动窗口 + 哈希表 |
| 滑动窗口 | 438 | 找到字符串中所有字母异位词 | 中等 | 滑动窗口 + 计数数组 |
| 滑动窗口 | 76 | 最小覆盖子串 | 困难 | 滑动窗口 + 频次统计 |
| 回文串 | 5 | 最长回文子串 | 中等 | 中心扩散 / 动态规划 |
| 回文串 | 647 | 回文子串 | 中等 | 中心扩散法 |
| 回文串 | 125 | 验证回文串 | 简单 | 左右双指针 |
| 字符串匹配 | 28 | 找出字符串中第一个匹配项的下标 | 简单 | KMP / 暴力匹配 |
| 哈希计数 | 242 | 有效的字母异位词 | 简单 | 数组计数 |
| 哈希计数 | 205 | 同构字符串 | 简单 | 双哈希映射 |
| 模拟变换 | 8 | 字符串转换整数 (atoi) | 中等 | 边界处理 + 符号判断 |
| 模拟变换 | 6 | Z 字形变换 | 中等 | 按行模拟 + 方向控制 |
面试官补充：字符串大多是基础送分题，核心是边界不出错、代码写整洁，中等题重点掌握滑动窗口和 KMP 思想，困难题一般是滑动窗口变形或字符串 DP。
真实面试模拟
真实面试模拟
面试官 😊：
欢迎来参加今天的面试，我们就聚焦一个经典方向——字符串算法。别紧张，咱们就是聊天式地过一下，你想到什么就说什么。
先来个热身：你觉得字符串这块，面试官通常在考察哪些核心能力？
候选人 🙋：
好的，我画个简单的脑图吧，基本能概括：
字符串算法核心能力
├─ 指针／索引精准控制 → 双指针、滑动窗口
├─ 回文、子串性质理解 → 中心扩展、动态规划
├─ 模式匹配能力 → KMP、Rabin-Karp
├─ 字符串与数字互转 → 大数加减乘除模拟
└─ 字符频率统计与排序 → 哈希表、桶排序字符串就是数组的变体，难点在于边界、空串、特殊字符，以及怎么把时间复杂度压下来。
面试官 👍：
总结得不错。那我们直接上题。
LeetCode 344 反转字符串，要求原地修改，你怎么写？
候选人 💻：
对撞双指针，非常直观：
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while (left < right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}面试官 🤔：
这里 while(left < right)，如果数组长度是偶数或奇数，会不会有问题？你心里怎么判断的？
候选人 🎯：
这个我一般会在纸上画一下：
- 长度 2：
left=0, right=1→ 交换后left=1, right=0→ 不满足<，退出，刚好。 - 长度 3：
left=0, right=2→ 交换后left=1, right=1→ 中间元素不动，退出。
所以条件用 < 是最安全的，不会越界也不会多交换。
面试官 🧐：
好。那我们加大点难度，LeetCode 3 无重复字符的最长子串，能说下思路再写吗？
候选人 💡：
典型的不定长滑动窗口。我维护一个窗口 [left, right)，用一个数组记录每个字符最新出现的位置+1。right 向右扩展，如果碰到重复字符，left 直接跳到记录的位置。窗口长度就是 right - left + 1。
public int lengthOfLongestSubstring(String s) {
int[] last = new int[128]; // ASCII字符集
int left = 0, max = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
left = Math.max(left, last[c]); // 碰到重复，left直接跳转
max = Math.max(max, right - left + 1);
last[c] = right + 1; // 更新下一跳位置
}
return max;
}这里用 last[c] 记录该字符下一个可以放置的位置，比用 HashSet 更省时间，O(n) 一把过。
面试官 ✨：
亮点是用数组代替哈希表、用跳跃代替逐步收缩。那滑动窗口的通用框架是怎样的？你画个流程图？
候选人 📈：
当然，我画个 Mermaid 吧：
技术难点：收缩条件写错，比如最小覆盖子串里，必须用一个 matchCount 来判断何时窗口完全覆盖目标。
解决方案：用计数数组 + 有效匹配数，避免每次都遍历检查。
面试官 🕵️：
刚才提到滑动窗口，那回文子串你会怎么处理？比如 LeetCode 5 最长回文子串。
候选人 🌟：
我偏爱中心扩展法，因为 O(n²) 时间、O(1) 空间，比 DP 更省内存。思路就是把每个位置当成中心，同时考虑奇数长度和偶数长度。
public String longestPalindrome(String s) {
int start = 0, maxLen = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expand(s, i, i); // 奇数中心
int len2 = expand(s, 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);
}
private int expand(String s, int left, int right) {
while (left >= 0 && right < s.length() &&
s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1; // 回文实际长度
}图示一下中心扩展：
奇数中心: i i
a b a ← 两边扩展
偶数中心: i i+1
a b b a技术难点：
- 长度计算公式
right - left - 1容易记错。 - 奇数/偶数中心起始索引别越界。
解决方案：用一个小例子（如 "aba"）心算一下 right - left - 1，然后记住。
面试官 🔍：
字符串匹配，经典的 KMP，你能讲一下 next 数组的含义，并手写一下 strStr 吗？
候选人 😅：
KMP 我虽然不能保证一次写对优化版 next，但我能写出清晰易懂的版本。
next[j] 表示：模式串在第 j 位失配时，应该跳转到哪个位置继续比较（即最长公共前后缀的长度）。
public int strStr(String haystack, String needle) {
if (needle.isEmpty()) return 0;
int n = haystack.length(), m = needle.length();
int[] next = buildNext(needle);
int i = 0, j = 0;
while (i < n && j < m) {
if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
i++; j++;
} else {
j = next[j];
}
}
return j == m ? i - j : -1;
}
private int[] buildNext(String pat) {
int m = pat.length();
int[] next = new int[m];
next[0] = -1;
int k = -1, j = 0;
while (j < m - 1) {
if (k == -1 || pat.charAt(j) == pat.charAt(k)) {
next[++j] = ++k;
} else {
k = next[k];
}
}
return next;
}技术难点：buildNext 里的 while 循环容易写成死循环，k = next[k] 回溯比较绕。
解决方案：面试时我会先画一个模式串 "ababc" 的前缀表，然后解释每一步回溯的意义，即使代码有小瑕疵，思路清晰也能过关。
面试官 🧮：
我们再看看字符串模拟大数运算，比如 LeetCode 415 字符串相加。
候选人 🧑💻：
这个就是模拟竖式加法，从右往左一位位加，处理好进位就行。
public String addStrings(String num1, String num2) {
StringBuilder sb = new StringBuilder();
int carry = 0;
int i = num1.length() - 1, j = num2.length() - 1;
while (i >= 0 || j >= 0 || carry > 0) {
int x = i >= 0 ? num1.charAt(i) - '0' : 0;
int y = j >= 0 ? num2.charAt(j) - '0' : 0;
int sum = x + y + carry;
sb.append(sum % 10);
carry = sum / 10;
i--; j--;
}
return sb.reverse().toString();
}技术难点：两个串长度不一、最后的进位别漏掉。
解决方案：循环条件加上 carry > 0，用一个变量统一处理。
面试官 📊：
咱们聊了不少了，你帮我把常见的高频字符串题分个类，最好有个速查表。
候选人 📋：
没问题，这个表格我给很多候选人都总结过：
| 类型 | 题号 | 题目 | 技巧标签 | 难度 |
|---|---|---|---|---|
| 反转类 | 344 | 反转字符串 | 双指针 | 🟢 |
| 反转类 | 151 | 翻转字符串里的单词 | 双指针/API | 🟡 |
| 子串问题 | 3 | 无重复字符的最长子串 | 滑动窗口 | 🟡 |
| 子串问题 | 76 | 最小覆盖子串 | 滑动窗口+哈希 | 🔴 |
| 回文 | 5 | 最长回文子串 | 中心扩展/DP | 🟡 |
| 回文 | 125 | 验证回文串 | 双指针+过滤 | 🟢 |
| 匹配 | 28 | 实现 strStr() | KMP/暴力 | 🟢 |
| 匹配 | 459 | 重复的子字符串 | KMP技巧 | 🟢 |
| 大数 | 415 | 字符串相加 | 模拟 | 🟢 |
| 大数 | 43 | 字符串相乘 | 模拟 | 🟡 |
| 排列组合 | 49 | 字母异位词分组 | 哈希+排序 | 🟡 |
| 编辑距离 | 72 | 编辑距离 | 二维DP | 🔴 |
| 子序列 | 392 | 判断子序列 | 双指针/DP | 🟢 |
面试官 🔥：
最后两个追问，考察你的工程意识。
① 如果字符串非常长，你的解法有性能瓶颈吗？
② 字符串里包含 emoji 😅 这种 Unicode 字符，你上面的代码还安全吗？
候选人 🤓：
- 第一个问题，我会分析复杂度：滑动窗口 O(n)，KMP O(n+m)，DP 可能是 O(n²)，能用中心扩展就别用 DP。空间上能用数组代替哈希表就一定省。
- 第二个问题，Java 里一个 emoji 可能占用两个 char（代理对），直接用
charAt会拆散。应该用codePointAt遍历代码点，或用Character.toChars()处理，回文判断也要基于代码点而非 char。
面试官 👍：
回答得很扎实，有理论有代码，还能考虑到 Unicode 这些细节。今天就到这里，感谢你的时间！
候选人 😄：
谢谢面试官，聊得很过瘾，也检验了自己的一些盲点！