02.2.2.2 字符串基础与子串变换
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.2 数组、字符串与哈希 / 02.2.2 字符串与哈希表
02.2.2.2-001 字符串为什么是不可变的?
一句话结论
字符串对象创建后内容不能修改,任何拼接/替换都生成新串;不可变使字符串可安全共享、作哈希键、缓存哈希码。
概念解释
- 不可变:内部字符数组只读。
- 修改:新建字符串复制结果。
- 收益:线程安全、可驻留、作 Map 键稳定。
原理流程
- 字符串构造后固定内容。
- 操作产生新对象。
- 原串保持不变。
代码 / 示例
String s = "ab";
String t = s + "c"; // t 是新对象,s 仍为 "ab"
常见误区
- 误区:
+修改原串;正解:生成新串,链式拼接平方级。 - 误区:字符串可以按下标赋值;正解:Java String 无 setCharAt,需转字符数组。
追问
- Q:可变等价物是什么? A:StringBuilder / StringBuffer。
- Q:不可变对哈希键有什么好处? A:哈希码不会漂移,可安全存入 HashMap。
02.2.2.2-002 char 与编码要注意什么?
一句话结论
Java char 是 UTF-16 代码单元,BMP 字符一个 char,增补字符占两个 char;按字符处理时注意代理对,长度与下标可能与视觉字符数不同。
概念解释
- 代码单元:char 16 位。
- 代理对:增补字符高低位两个 char。
- 长度:
length()是代码单元数。
原理流程
- 判断是否含增补字符。
- 需要按字符处理时用码点遍历。
- 下标操作注意代理对边界。
代码 / 示例
int[] codePoints = s.codePoints().toArray(); // 按码点遍历
常见误区
- 误区:char 数等于字符数;正解:增补字符占两个 char。
- 误区:直接按 char 反转含 emoji 的串;正解:可能切断代理对。
追问
- Q:题目字符集限定小写字母? A:单 char 即可,数组计数 26。
- Q:中文在 char 中怎么存? A:常见中文在 BMP 内单 char,具体以编码为准。
02.2.2.2-003 反转字符串(LC 344)怎么做?
一句话结论
字符数组相向双指针交换对称位置;原地 O(n) 时间 O(1) 空间;题目给字符数组,避免字符串不可变问题。
概念解释
- 原地交换。
- 到中点停止。
- 奇数长度中位不动。
原理流程
- l=0,r=len-1。
- 交换并内移。
- l≥r 结束。
代码 / 示例
public void reverseString(char[] s) {
int l = 0, r = s.length - 1;
while (l < r) {
char t = s[l]; s[l++] = s[r]; s[r--] = t;
}
}
常见误区
- 误区:新建数组倒序拷贝;正解:原地交换省空间。
- 误区:处理代理对直接按 char 换;正解:增补字符需按码点分段。
追问
- Q:空数组/单元素? A:循环不执行,直接返回。
- Q:返回新字符串怎么做? A:字符数组反转后 new String。
02.2.2.2-004 反转字符串 II(LC 541)按段反转怎么做?
一句话结论
每 2k 个字符为一段,反转前 k 个,后 k 个保留;不足 k 个则反转到末尾;按段起点步进 2k。
概念解释
- 段长 2k。
- 段内前 k 反转。
- 末尾截断处理。
原理流程
- 起点 i=0。
- 每段确定反转右端
min(i+k-1, n-1)。 - 局部反转后 i += 2k。
代码 / 示例
public String reverseStr(String s, int k) {
char[] a = s.toCharArray();
int n = a.length;
for (int i = 0; i < n; i += 2 * k) {
int l = i, r = Math.min(i + k - 1, n - 1);
while (l < r) { char t = a[l]; a[l++] = a[r]; a[r--] = t; }
}
return new String(a);
}
常见误区
- 误区:右端不截断;正解:末尾不足 k 时按 n-1 收尾。
- 误区:每段反转全部 2k;正解:只反转前 k。
追问
- Q:k=1? A:字符串不变。
- Q:k ≥ n? A:整体反转一次。
02.2.2.2-005 替换空格怎么写?
一句话结论
字符数组原地扩容或新建结果串:遇到空格替换为目标串,非空格原样拷贝;先统计空格数确定结果长度,避免反复扩容。
概念解释
- 替换变长:空格 → 多字符。
- 预分配:统计后定长。
- 从后向前原地填可避免覆盖。
原理流程
- 统计空格数。
- 计算结果长度。
- 双指针从后向前拷贝替换。
代码 / 示例
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder(s.length() * 3);
for (char c : s.toCharArray()) {
if (c == ' ') sb.append("%20");
else sb.append(c);
}
return sb.toString();
}
常见误区
- 误区:循环内
+拼接;正解:用 StringBuilder 避免平方级。 - 误区:原地替换未预留长度;正解:变长替换必须先算结果长度。
追问
- Q:从后向前原地替换为什么不覆盖? A:写指针落后于读指针,空位足够。
- Q:替换为等长字符? A:可直接原地赋值。
02.2.2.2-006 字符串压缩(LC 443)怎么做?
一句话结论
快慢指针扫描连续重复段:慢指针写压缩结果,快指针数连续相同字符;重复次数转字符串追加;原地修改字符数组,返回新长度。
概念解释
- 游程编码:字符 + 重复次数。
- 次数 1 不追加数字。
- 结果可能短于原串。
原理流程
- 读指针统计同字符段长。
- 写指针落字符与次数。
- 返回写指针长度。
代码 / 示例
public int compress(char[] a) {
int w = 0;
for (int r = 0; r < a.length; ) {
int l = r;
while (r < a.length && a[r] == a[l]) r++;
a[w++] = a[l];
if (r - l > 1) {
for (char c : String.valueOf(r - l).toCharArray()) a[w++] = c;
}
}
return w;
}
常见误区
- 误区:次数多位数字只写一位;正解:次数转字符串逐位写入。
- 误区:压缩后长度可能变长;正解:题目保证结果可放入原数组口径内。
追问
- Q:次数为 1 怎么处理? A:只写字符,不写 1。
- Q:压缩率怎么评估? A:重复段越长压缩越好。
02.2.2.2-007 有效字母异位词(LC 242)怎么判断?
一句话结论
两串长度相同且字符计数一致即异位词;小字符集用 26 计数数组,O(n) 时间 O(1) 空间;也可排序比较,但 O(n log n)。
概念解释
- 异位词:字符多重集合相同。
- 计数表逐字符抵消。
- 长度不同直接排除。
原理流程
- 长度不等返回 false。
- 计数表先加后减。
- 全表为 0 即匹配。
代码 / 示例
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] cnt = new int[26];
for (char c : s.toCharArray()) cnt[c - 'a']++;
for (char c : t.toCharArray()) cnt[c - 'a']--;
for (int x : cnt) if (x != 0) return false;
return true;
}
常见误区
- 误区:先排序再比较;正解:计数表线性更优。
- 误区:含大写/其他字符仍用 26 数组;正解:按实际字符集开大或用哈希。
追问
- Q:Unicode 字符怎么计数? A:用码点计数或哈希表。
- Q:空格算不算字符? A:按题面口径纳入计数。
02.2.2.2-008 分组字母异位词(LC 49)怎么做?
一句话结论
以排序后的串(或计数串)为哈希键,原串归入对应分组;O(n·k log k)(排序键)或 O(n·k)(计数键),空间 O(nk)。
概念解释
- 键:同组异位词的规范表示。
- 值:原串列表。
- 两种键:排序串 / 计数串。
原理流程
- 遍历每个串生成规范键。
- 哈希分组。
- 输出各组列表。
代码 / 示例
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] c = s.toCharArray();
Arrays.sort(c);
String key = new String(c);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
常见误区
- 误区:用原串作键;正解:异位词原串不同,需规范键。
- 误区:计数键拼接分隔符;正解:位数歧义时加分隔或用定长编码。
追问
- Q:计数键怎么构造? A:26 计数转成带分隔的字符串,避免 1,2 与 12 混淆。
- Q:最长串长度 k 影响复杂度? A:计入每串处理代价。
02.2.2.2-009 最长公共前缀(LC 14)怎么求?
一句话结论
以第一串为基准逐列比较所有串;某列字符不一致或某串到末尾即停止;O(n·k) 时间 O(1) 额外空间。
概念解释
- 公共前缀:所有串开头共有部分。
- 纵向扫描:按列对齐比较。
- 最短串长度为上界。
原理流程
- 取第一串逐字符。
- 与其余串同列比较。
- 不一致即返回当前前缀。
代码 / 示例
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
for (int i = 0; i < strs[0].length(); i++) {
char c = strs[0].charAt(i);
for (String s : strs) {
if (i == s.length() || s.charAt(i) != c) return strs[0].substring(0, i);
}
}
return strs[0];
}
常见误区
- 误区:横向两两求前缀;正解:纵向扫描更直接,提前终止。
- 误区:不判短串越界;正解:先比较长度再取字符。
追问
- Q:空数组? A:返回空串。
- Q:二分法可行吗? A:可按前缀长度二分比较,O(n·k log k)。
02.2.2.2-010 字符串大数相加(LC 415)怎么做?
一句话结论
从末位逐位相加,维护进位;结果倒序拼接;处理两串长度差与最高位进位;O(max(n,m)) 时间。
概念解释
- 手工竖式:低位起加。
- 进位:超过 10 留进位。
- 结果反转。
原理流程
- i、j 从末尾起。
- 逐位加和加进位。
- 记录个位,更新进位。
- 收尾进位并反转。
代码 / 示例
public String addStrings(String a, String b) {
StringBuilder sb = new StringBuilder();
int i = a.length() - 1, j = b.length() - 1, carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
int x = i >= 0 ? a.charAt(i--) - '0' : 0;
int y = j >= 0 ? b.charAt(j--) - '0' : 0;
int sum = x + y + carry;
sb.append(sum % 10);
carry = sum / 10;
}
return sb.reverse().toString();
}
常见误区
- 误区:转整数相加;正解:大数超出类型范围,必须按位模拟。
- 误区:最高位进位遗漏;正解:循环条件带 carry > 0。
追问
- Q:负数大数相加? A:先处理符号,转化为绝对值加减。
- Q:位字符转数字? A:
c - '0'。
02.2.2.2-011 字符串相乘(LC 43)怎么做?
一句话结论
两数各位乘积落位:num1[i] × num2[j] 贡献到结果下标 i+j 与 i+j+1;先按位累积再统一处理进位;O(n·m)。
概念解释
- 乘积位:第 i 位与第 j 位乘积落在 i+j 高位与 i+j+1 低位。
- 累积:先存原始积,再整理进位。
- 去前导零。
原理流程
- 结果数组长度 n+m。
- 双重循环按位乘积累加。
- 从低位整理进位。
- 转字符串去零。
代码 / 示例
public String multiply(String num1, String num2) {
int n = num1.length(), m = num2.length();
int[] p = new int[n + m];
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
int sum = mul + p[i + j + 1];
p[i + j + 1] = sum % 10;
p[i + j] += sum / 10;
}
}
StringBuilder sb = new StringBuilder();
for (int v : p) if (!(sb.length() == 0 && v == 0)) sb.append(v);
return sb.length() == 0 ? "0" : sb.toString();
}
常见误区
- 误区:逐位乘后立即进位;正解:先累积到对应位,最后统一整理。
- 误区:结果前导零未去除;正解:开头零跳过,全零返回 "0"。
追问
- Q:为什么结果长度 n+m? A:两数乘积位数不超过位数和。
- Q:乘数含零? A:结果数组全零,最终返回 "0"。
02.2.2.2-012 Z 字形变换(LC 6)怎么排?
一句话结论
按行维护 StringBuilder,字符在行数间上下往返;方向到顶/到底反转;最后拼接各行;O(n) 时间 O(n) 空间。
概念解释
- 行号:向下递增,触底转向上。
- 方向:step = ±1。
- 拼接:按行输出。
原理流程
- 建 rows 个缓冲。
- 逐字符落当前行,更新行号与方向。
- 合并各行。
代码 / 示例
public String convert(String s, int numRows) {
if (numRows == 1) return s;
StringBuilder[] rows = new StringBuilder[numRows];
for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
int row = 0, step = 1;
for (char c : s.toCharArray()) {
rows[row].append(c);
if (row == 0) step = 1;
else if (row == numRows - 1) step = -1;
row += step;
}
StringBuilder ans = new StringBuilder();
for (StringBuilder r : rows) ans.append(r);
return ans.toString();
}
常见误区
- 误区:numRows=1 仍跑方向逻辑;正解:直接返回原串。
- 误区:方向在边界更新顺序错位;正解:先落字符再判边界转向。
追问
- Q:行数大于串长? A:每行至多一字符,按顺序落行。
- Q:数学直写映射? A:可按周期
2(numRows-1)计算列位置。
02.2.2.2-013 翻转字符串里的单词(LC 151)怎么做?
一句话结论
先去除首尾与多余空格,按空格切分后逆序拼接;或整体反转再逐词反转;O(n) 时间,注意多空格压缩。
概念解释
- 规范:单词间单空格,首尾无空格。
- 两种思路:切分逆序 / 两次反转。
- 空格处理是边界重点。
原理流程
- 规范化空格。
- 切分单词列表。
- 逆序拼接。
代码 / 示例
public String reverseWords(String s) {
String[] words = s.trim().split("\\s+");
StringBuilder sb = new StringBuilder();
for (int i = words.length - 1; i >= 0; i--) {
sb.append(words[i]);
if (i > 0) sb.append(' ');
}
return sb.toString();
}
常见误区
- 误区:直接按单空格 split;正解:多空格需正则
\s+或手动跳过。 - 误区:末尾多拼空格;正解:按索引判断分隔符。
追问
- Q:两次反转法怎么写? A:整体反转 → 每词内部反转 → 清理空格。
- Q:题目要求原地吗? A:Java 字符串不可变,通常用字符数组模拟。
02.2.2.2-014 字符串中第一个唯一字符(LC 387)怎么做?
一句话结论
计数表先统计出现次数,再扫描找第一个次数为 1 的字符;O(n) 时间 O(字符集) 空间。
概念解释
- 两次扫描:计数 + 定位。
- 唯一性:次数恰好 1。
- 保持原顺序。
原理流程
- 一遍计数。
- 二遍按序查次数。
- 返回首个单字符下标。
代码 / 示例
public int firstUniqChar(String s) {
int[] cnt = new int[26];
for (char c : s.toCharArray()) cnt[c - 'a']++;
for (int i = 0; i < s.length(); i++)
if (cnt[s.charAt(i) - 'a'] == 1) return i;
return -1;
}
常见误区
- 误区:一遍扫描边查边定;正解:需先知道全串次数,两遍稳妥。
- 误区:返回字符而非下标;正解:按题目口径返回下标。
追问
- Q:字符集不限小写? A:用哈希表计数。
- Q:多次询问首个唯一? A:队列维护候选与计数,在线淘汰。
02.2.2.2-015 比较版本号(LC 165)怎么做?
一句话结论
按点切分修订号,逐段转整数比较;缺段视为 0;前导零按数值忽略;O(n+m) 时间。
概念解释
- 修订号:点分隔各段。
- 数值比较:忽略前导零。
- 长度不齐补零。
原理流程
- 切分两版本。
- 逐段数值比较。
- 超长段补零继续。
代码 / 示例
public int compareVersion(String v1, String v2) {
String[] a = v1.split("\\.");
String[] b = v2.split("\\.");
int n = Math.max(a.length, b.length);
for (int i = 0; i < n; i++) {
int x = i < a.length ? Integer.parseInt(a[i]) : 0;
int y = i < b.length ? Integer.parseInt(b[i]) : 0;
if (x != y) return x < y ? -1 : 1;
}
return 0;
}
常见误区
- 误区:按字符串字典序比较;正解:段内按数值,前导零不影响。
- 误区:短版本结束即停止;正解:剩余段按 0 参与比较。
追问
- Q:段号超大? A:按题意可能需大整数比较,避免 parseInt 溢出。
- Q:忽略末尾零段? A:题目口径内 1.0 与 1.0.0 视为相等。
02.2.2.2-016 字符串与字符数组如何互转?
一句话结论
toCharArray() 转字符数组,new String(char[]) 转回;数组可原地修改,字符串不可变;修改场景先转数组再转串。
概念解释
- 转换有拷贝成本。
- 数组原地改,串新建。
- 热循环避免反复互转。
原理流程
- 需要修改时转数组。
- 数组上操作。
- 结果转回字符串。
代码 / 示例
char[] a = s.toCharArray();
// 原地修改 a
String t = new String(a);
常见误区
- 误区:反复 toCharArray 造成多次拷贝;正解:一次转换后完成所有修改。
- 误区:修改数组影响原串;正解:toCharArray 是拷贝。
追问
- Q:StringBuilder 内部是什么? A:可变字符序列,按需扩容。
- Q:截取子串代价? A:按实现可能拷贝字符,注意不可假设 O(1)。
02.2.2.2-017 子串与子序列有什么区别?
一句话结论
子串连续取原串一段;子序列可不连续但保持相对顺序;连续问题用窗口/双指针,子序列问题用贪心/DP。
概念解释
- 子串:位置连续。
- 子序列:下标递增即可。
- 算法框架不同。
原理流程
- 判断题中是否要求连续。
- 连续套窗口/前缀和。
- 不连续套双指针匹配或 DP。
代码 / 图示
"abc" 子串:"ab"、"bc"
子序列:"ac"(不连续)
常见误区
- 误区:子序列也用滑动窗口;正解:不连续窗口不适用。
- 误区:子串可以跳字符;正解:子串必须连续。
追问
- Q:最长公共子序列用什么? A:二维 DP,见动态规划分册。
- Q:最长公共子串用什么? A:连续匹配,DP 或窗口。
02.2.2.2-018 字符串题的边界用例有哪些?
一句话结论
空串、单字符、全相同、全部不同、首尾字符、含空格/符号、长度不等、大小写混合;先覆盖这些再谈正常用例。
概念解释
- 空与最短:验证初始条件。
- 重复分布:验证计数与窗口。
- 特殊字符:验证过滤规则。
原理流程
- 入口判空。
- 构造长度 0/1。
- 构造重复与符号用例。
代码 / 图示
"" / "a" / "aaa" / "abc"
"a b c" / "Aab" / 含数字符号
两串长度不等
常见误区
- 误区:默认串非空;正解:入口先判长度。
- 误区:大小写视为相同;正解:按题面口径是否归一化。
追问
- Q:空串返回什么类型? A:按题目返回 ""、0、false 或空列表。
- Q:首尾空格算字符吗? A:按题面要求过滤或保留。
02.2.2.2-019 字符串拼接为什么要用 StringBuilder?
一句话结论
不可变串链式 + 每步复制旧内容,O(n²);StringBuilder 内部可变缓冲按需扩容,摊还 O(n);预知长度时预分配容量。
概念解释
- 不可变复制:每步新建。
- 缓冲追加:一次扩容多次写。
- 预分配:避免中途扩容。
原理流程
- 识别循环内拼接。
- 用 StringBuilder。
- 预估容量减少扩容。
代码 / 示例
StringBuilder sb = new StringBuilder(totalLen);
for (String w : words) sb.append(w);
常见误区
- 误区:编译器总会优化循环拼接;正解:不要依赖,显式用 Builder。
- 误区:StringBuilder 线程安全;正解:StringBuffer 才加锁,Builder 单线程更快。
追问
- Q:少量拼接直接
+有问题吗? A:固定个数常数小,可读性优先。 - Q:预估容量怎么算? A:累加各片段长度。
02.2.2.2-020 字符串题复杂度怎么汇报?
一句话结论
设串长 n、多串总字符 N;扫描类 O(n),排序键类 O(n log n) 或 O(n·k log k),计数表空间 O(字符集);汇报时分串数与单串长度。
概念解释
- 单串长度 n。
- 多串:串数 × 单串长。
- 空间:计数表或结果串。
原理流程
- 统计串数与平均长度。
- 标注每串处理代价。
- 辅助结构空间。
代码 / 图示
单串扫描:O(n),空间 O(字符集)
分组异位词:O(n·k log k),空间 O(nk)
常见误区
- 误区:只说 O(n) 不说是串长还是串数;正解:口径写清。
- 误区:忽略结果串空间;正解:输出空间按题面口径单列。
追问
- Q:字符集固定为何空间 O(1)? A:计数表大小与 n 无关。
- Q:正则匹配复杂度? A:按正则实现与引擎而定,标注待确认具体行为。