罗罗编程学习记录
本页内容 展开查看

02.2.2.2 字符串基础与子串变换

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.2 数组、字符串与哈希 / 02.2.2 字符串与哈希表

02.2.2.2-001 字符串为什么是不可变的?

一句话结论

字符串对象创建后内容不能修改,任何拼接/替换都生成新串;不可变使字符串可安全共享、作哈希键、缓存哈希码。

概念解释

  • 不可变:内部字符数组只读。
  • 修改:新建字符串复制结果。
  • 收益:线程安全、可驻留、作 Map 键稳定。

原理流程

  1. 字符串构造后固定内容。
  2. 操作产生新对象。
  3. 原串保持不变。

代码 / 示例

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() 是代码单元数。

原理流程

  1. 判断是否含增补字符。
  2. 需要按字符处理时用码点遍历。
  3. 下标操作注意代理对边界。

代码 / 示例

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) 空间;题目给字符数组,避免字符串不可变问题。

概念解释

  • 原地交换。
  • 到中点停止。
  • 奇数长度中位不动。

原理流程

  1. l=0,r=len-1。
  2. 交换并内移。
  3. 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 反转。
  • 末尾截断处理。

原理流程

  1. 起点 i=0。
  2. 每段确定反转右端 min(i+k-1, n-1)。
  3. 局部反转后 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 替换空格怎么写?

一句话结论

字符数组原地扩容或新建结果串:遇到空格替换为目标串,非空格原样拷贝;先统计空格数确定结果长度,避免反复扩容。

概念解释

  • 替换变长:空格 → 多字符。
  • 预分配:统计后定长。
  • 从后向前原地填可避免覆盖。

原理流程

  1. 统计空格数。
  2. 计算结果长度。
  3. 双指针从后向前拷贝替换。

代码 / 示例

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 不追加数字。
  • 结果可能短于原串。

原理流程

  1. 读指针统计同字符段长。
  2. 写指针落字符与次数。
  3. 返回写指针长度。

代码 / 示例

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)。

概念解释

  • 异位词:字符多重集合相同。
  • 计数表逐字符抵消。
  • 长度不同直接排除。

原理流程

  1. 长度不等返回 false。
  2. 计数表先加后减。
  3. 全表为 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)。

概念解释

  • 键:同组异位词的规范表示。
  • 值:原串列表。
  • 两种键:排序串 / 计数串。

原理流程

  1. 遍历每个串生成规范键。
  2. 哈希分组。
  3. 输出各组列表。

代码 / 示例

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) 额外空间。

概念解释

  • 公共前缀:所有串开头共有部分。
  • 纵向扫描:按列对齐比较。
  • 最短串长度为上界。

原理流程

  1. 取第一串逐字符。
  2. 与其余串同列比较。
  3. 不一致即返回当前前缀。

代码 / 示例

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 留进位。
  • 结果反转。

原理流程

  1. i、j 从末尾起。
  2. 逐位加和加进位。
  3. 记录个位,更新进位。
  4. 收尾进位并反转。

代码 / 示例

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 低位。
  • 累积:先存原始积,再整理进位。
  • 去前导零。

原理流程

  1. 结果数组长度 n+m。
  2. 双重循环按位乘积累加。
  3. 从低位整理进位。
  4. 转字符串去零。

代码 / 示例

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。
  • 拼接:按行输出。

原理流程

  1. 建 rows 个缓冲。
  2. 逐字符落当前行,更新行号与方向。
  3. 合并各行。

代码 / 示例

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) 时间,注意多空格压缩。

概念解释

  • 规范:单词间单空格,首尾无空格。
  • 两种思路:切分逆序 / 两次反转。
  • 空格处理是边界重点。

原理流程

  1. 规范化空格。
  2. 切分单词列表。
  3. 逆序拼接。

代码 / 示例

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。
  • 保持原顺序。

原理流程

  1. 一遍计数。
  2. 二遍按序查次数。
  3. 返回首个单字符下标。

代码 / 示例

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) 时间。

概念解释

  • 修订号:点分隔各段。
  • 数值比较:忽略前导零。
  • 长度不齐补零。

原理流程

  1. 切分两版本。
  2. 逐段数值比较。
  3. 超长段补零继续。

代码 / 示例

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[]) 转回;数组可原地修改,字符串不可变;修改场景先转数组再转串。

概念解释

  • 转换有拷贝成本。
  • 数组原地改,串新建。
  • 热循环避免反复互转。

原理流程

  1. 需要修改时转数组。
  2. 数组上操作。
  3. 结果转回字符串。

代码 / 示例

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。

概念解释

  • 子串:位置连续。
  • 子序列:下标递增即可。
  • 算法框架不同。

原理流程

  1. 判断题中是否要求连续。
  2. 连续套窗口/前缀和。
  3. 不连续套双指针匹配或 DP。

代码 / 图示

"abc" 子串:"ab"、"bc"
子序列:"ac"(不连续)

常见误区

  • 误区:子序列也用滑动窗口;正解:不连续窗口不适用。
  • 误区:子串可以跳字符;正解:子串必须连续。

追问

  • Q:最长公共子序列用什么? A:二维 DP,见动态规划分册。
  • Q:最长公共子串用什么? A:连续匹配,DP 或窗口。

02.2.2.2-018 字符串题的边界用例有哪些?

一句话结论

空串、单字符、全相同、全部不同、首尾字符、含空格/符号、长度不等、大小写混合;先覆盖这些再谈正常用例。

概念解释

  • 空与最短:验证初始条件。
  • 重复分布:验证计数与窗口。
  • 特殊字符:验证过滤规则。

原理流程

  1. 入口判空。
  2. 构造长度 0/1。
  3. 构造重复与符号用例。

代码 / 图示

"" / "a" / "aaa" / "abc"
"a b  c" / "Aab" / 含数字符号
两串长度不等

常见误区

  • 误区:默认串非空;正解:入口先判长度。
  • 误区:大小写视为相同;正解:按题面口径是否归一化。

追问

  • Q:空串返回什么类型? A:按题目返回 ""、0、false 或空列表。
  • Q:首尾空格算字符吗? A:按题面要求过滤或保留。

02.2.2.2-019 字符串拼接为什么要用 StringBuilder?

一句话结论

不可变串链式 + 每步复制旧内容,O(n²);StringBuilder 内部可变缓冲按需扩容,摊还 O(n);预知长度时预分配容量。

概念解释

  • 不可变复制:每步新建。
  • 缓冲追加:一次扩容多次写。
  • 预分配:避免中途扩容。

原理流程

  1. 识别循环内拼接。
  2. 用 StringBuilder。
  3. 预估容量减少扩容。

代码 / 示例

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。
  • 多串:串数 × 单串长。
  • 空间:计数表或结果串。

原理流程

  1. 统计串数与平均长度。
  2. 标注每串处理代价。
  3. 辅助结构空间。

代码 / 图示

单串扫描:O(n),空间 O(字符集)
分组异位词:O(n·k log k),空间 O(nk)

常见误区

  • 误区:只说 O(n) 不说是串长还是串数;正解:口径写清。
  • 误区:忽略结果串空间;正解:输出空间按题面口径单列。

追问

  • Q:字符集固定为何空间 O(1)? A:计数表大小与 n 无关。
  • Q:正则匹配复杂度? A:按正则实现与引擎而定,标注待确认具体行为。