tech-interview-handbook 字符串算法速查手册：时间复杂度、面试技巧与必练题目全解

本文基于 tech-interview-handbook 仓库中的字符串主题速查文档（string.md），系统梳理字符串在编码面试中的基本定位、操作时间复杂度、面试前必问的确认事项、边角情况以及字符计数、Anagram（变位词）、Palindrome（回文）三大核心解题技巧，并结合仓库内置的 Rabin-Karp 滚动哈希、素数映射、Trie 等参考实现，帮助读者把每个技巧落实为可复现、可解释的面试答案。

字符串：编码面试中最基础的序列类型

字符串是字符的序列。由于字符串本质上就是字符数组，凡是适用于数组的技巧，绝大多数同样适用于字符串题。仓库中的 数组速查文档 也明确写道：因为数组和字符串都是序列（字符串是字符数组），其中讲的滑动窗口、双指针等技巧大多可以直接迁移到字符串问题上。因此，建议在阅读本主题之前先掌握数组相关内容。

从 面试题型优先级表 可以看到，String 在仓库中被标注为 High 优先级，是面试备考的核心模块之一。

字符串查找的常见数据结构

• Trie / Prefix Tree（前缀树）：按字符逐层组织字符串，适合前缀匹配、词频统计等场景
• Suffix Tree（后缀树）：基于所有后缀构建的树结构，适合复杂的子串匹配问题

仓库内提供了一个可直接运行的 Trie 参考实现 trie.py，其 insert、search、startsWith 三个方法展示了核心思想：每个节点是一个 dict，键为字符、值为子节点；词尾用一个 '#' 键做标记（注释说明：用空 dict 而非布尔值是为了让递归遍历更方便）。此外它还有一个 searchRegex 方法，支持用 . 通配任意一个字符——面试中遇到“带通配符的前缀匹配”类问题时，这个递归遍历模式可以直接借鉴。

常见的字符串算法

• Rabin-Karp：利用滚动哈希（rolling hash）高效搜索子串
• KMP：Knuth-Morris-Pratt 算法，通过预处理失配表实现高效的子串搜索

Rabin-Karp 是字符串题中唯一值得在面试中口头展开的算法，仓库里恰好有一份完整的 Python 实现 rabin_karp_hash.py，其文件头注释把核心思想讲得很清楚：滚动哈希用于计算连续子串的哈希值。例如从 'abcd' 滑到 'bcde'，只需从左侧剔除 'a'、在右侧补入 'e'，哈希值可以在 O(1) 内原地更新，而不必重新计算整个长度为 m 的子串哈希的 O(m) 开销。

核心实现只有两个函数，选取一个任意素数作为底数（示例中 BASE = 101）：

BASE = 101  # Arbitrary prime number

def rk_hash_init(tpl):
    '''Initializes the hash with a tuple of integers.'''
    return sum(n * BASE ** i for i, n in enumerate(reversed(tpl)))

def rk_hash_update(curr_hash, size, add_n, rem_n):
    '''Updates the hash by removing an integer from the left and appending
    an integer to the right.

    curr_hash: The previous hash
    size: The size of the rolling window
    add_n: The integer appended to the right
    rem_n: The integer removed from the left'''
    return (curr_hash - (rem_n * BASE ** (size - 1))) * BASE + add_n

其使用方式是把字符串中每个字符先取 ASCII 值（ord）再传入。实现里给出了一个很好的自验证示例：分别以 'abc' 和 'zbc' 为起点，各执行一次滚动更新到 'bcd'，两条路径得到的哈希值相等（bcd_hash_1 == bcd_hash_2 为 True），说明滚动更新与重新计算是等价的。该实现刻意接收整型元组而非字符串，以保持通用性——字符串只是把 ord(c) 代入即可。

字符串操作的时间复杂度

由于字符串是字符数组，基本字符串操作的时间复杂度与数组操作高度相似。设字符串长度为 n：

Operation	Big-O
Access	O(1)
Search	O(n)
Insert	O(n)
Remove	O(n)

涉及另一个字符串的操作

设另一个字符串长度为 m：

Operation	Big-O	Note
Find substring	O(n.m)	最朴素的暴力情况；存在 KMP 等更高效的字符串搜索算法
Concatenating strings	O(n + m)
Slice	O(m)
Split (by token)	O(n + m)
Strip (remove leading and trailing whitespaces)	O(n)

面试中需要特别注意：在 Python、JavaScript 等语言里拼接、切片字符串看似简单，但都是 O(n) 级别的操作。如果在一个循环里反复拼接字符串，累积起来会把本应 O(n) 的解法拖成 O(n²)，这与 数组速查文档 中提醒“尽量用起止下标标记子区间，而不是频繁 slice/拼接”的原则一致。

面试中要先确认的事项

原文档给出的关键提醒只有一条，但非常实用：

先问清楚输入的字符集（character set）和是否区分大小写（case sensitivity）。 通常题目会限定字符只包含小写拉丁字母，即 a 到 z。这个确认直接影响你的空间复杂度结论——后文“字符计数”一节中，计数器空间为什么是 O(1) 而不是 O(n)，就完全取决于这个前提。

必须考虑的边角情况（Corner cases）

提交代码前过一遍这四类输入：

• 空字符串（Empty string）
• 只有 1 个或 2 个字符的字符串
• 含重复字符的字符串
• 全部字符互不相同的字符串

核心解题技巧

原文档将字符串题归纳为三大类。

技巧一：统计字符（Counting characters）

字符频率统计是字符串题中出现频率最高的子任务。最通用的做法是用语言内置的哈希表/字典来计数；如果语言自带类似 Python collections.Counter 的现成工具，先询问面试官是否允许使用（仓库的文档原话是：ask if you can use that instead）。

一个高频易错点：当你需要为字符串维护一个字符计数器时，很多人会说计数器占 O(n) 空间。这是错的。对于拉丁字符字符串，计数器所需空间是 O(1) 而不是 O(n)——因为计数器键空间的上界是字符集大小，即通常固定的 26（输入集限定为小写拉丁字母），与字符串长度 n 无关。

进阶：用 26 位位掩码表示唯一字符字符串

如果字符串的字符保证互不相同，有一个精巧的技巧：用一个 26 位位掩码（bitmask）来标记哪些小写字母出现在字符串中，文档给出的实现如下：

mask = 0
for c in word:
  mask |= (1 << (ord(c) - ord('a')))

判断两个字符串是否有公共字符时，只需对两个位掩码做按位与：若 mask_a & mask_b > 0（结果非零），则两个字符串存在公共字符。这比用集合求交更快，且只需 O(1) 空间——是“字符集固定为 26 个小写字母”这一前提下最极致的空间优化。

技巧二：Anagram（变位词）判定

Anagram（词元换位）是指重排一个单词或短语中的字母得到新单词或短语，且每个原始字母只用一次。在面试中，通常只处理不含空格的单词。判定两个字符串是否为 anagram，文档给出三种方法及各自的复杂度：

1. 排序法：两个字符串分别排序后应得到相同字符串。时间 O(n.log(n))，空间 O(n)。
2. 素数乘积法：把每个字符映射到一个素数，再把所有映射值相乘；anagram 的乘积必然相同（依据唯一分解定理，即素数因子分解唯一）。时间 O(n)，空间 O(1)。
3. 频率计数法：统计每个字符的出现次数并比较，anagram 的计数结果应完全一致。时间 O(n)，空间 O(1)。

仓库中恰好有素数乘积法的现成实现 char_prime_map.py，文件注释说明其用途正是“检查两个字符串是否互为 anagram 或排列”：

# For mapping a lowercase character to a prime number.
# Useful for checking whether two strings are anagram or permutations of each other.
primes = {
    'a': 2, 'b': 3, 'c': 5, 'd': 7, 'e': 11, 'f': 13,
    'g': 17, 'h': 19, 'i': 23, 'j': 29, 'k': 31, 'l': 37,
    'm': 41, 'n': 43, 'o': 47, 'p': 53, 'q': 59, 'r': 61,
    's': 67, 't': 71, 'u': 73, 'v': 79, 'w': 83, 'x': 89,
    'y': 97, 'z': 101, ' ': 103,
}

import functools

def mul(seq):
    return functools.reduce(lambda a, b: a * b, seq, 1)

def prime_value_of_string(string):
    return mul([primes[c] for c in string])

可以看到 26 个小写字母被依次映射为前 26 个素数（2 到 101），并额外为空格预留了 103。面试中若用此方法，可以顺带提醒：乘积增长很快，实际语言实现中通常需要取模或考虑大整数，但复杂度分析上仍按 O(n) 时间、O(1) 空间计。

技巧三：Palindrome（回文）判定

Palindrome 是正读和反读都相同的字符串，如 madam、racecar。判定方法有两种：

1. 反转比较：把字符串反转后应与自身相等。
2. 双向双指针：两个指针分别置于字符串首尾，向中间移动直到相遇；任一时刻两个指针所指字符都应相等。

注意：回文判定依赖字符在字符串中的顺序，因此哈希表这类与顺序无关的工具通常帮不上忙。

当题目变成统计回文个数时，常用技巧是双指针从中心向外扩展。由于回文长度可奇可偶，每个中心位置要检查两次——一次以该字符为中心（奇数长度）、一次以该字符与相邻字符之间为中心（偶数长度）。这是 LeetCode “Longest Palindromic Substring”（最长回文子串）的标准解法。

文档还区分了两个容易混淆的场景：

• 子串（substring）场景：一旦向外扩展不再匹配就可以提前终止（early termination）；
• 子序列（subsequence）场景：由于存在重叠子问题，应使用动态规划求解（对应 LeetCode “Longest Palindromic Subsequence”）。

关于“子序列”这一概念，仓库提供了一个双指针顺序匹配的可运行实现 is_subsequence.py（同名 JavaScript 版为 isSubsequence.js）：用一个 matched_s 计数已匹配的前缀长度，遍历 t 的每个字符，命中则前缀前进一格，最终 matched_s == len(s) 即为子序列。它的时间复杂度是 O(len(t))，可以作为面试中口头解释“子序列不要求连续、但要求保序”时的演示示例。

Essential Questions（必练习题）

原文档指定了学习该主题时必须练习的三道核心题：

• Valid Anagram（有效的变位词）——直接考察频率计数法
• Valid Palindrome（有效的回文串）——考察双指针，且需注意“只考虑字母数字字符、忽略大小写”的预处理
• Longest Substring Without Repeating Characters（无重复字符的最长子串）——考察滑动窗口 + 字符集计数，是“字符串是数组”这一视角的典型应用

Recommended Practice Questions（进阶练习题）

完成必练三题后，原文档推荐以下进阶题：

• Longest Repeating Character Replacement（最长重复字符替换）
• Find All Anagrams in a String（找出字符串中所有字母异位词）——滑动窗口 + 字符计数的经典组合
• Minimum Window Substring（最小覆盖子串）——滑动窗口的压轴题
• Group Anagrams（字母异位词分组）——考察以排序结果或频率序列作为哈希键
• Longest Palindromic Substring（最长回文子串）——中心扩展法实战
• Encode and Decode Strings（字符串编码与解码，LeetCode Premium 题）

学习路径建议

原文档末尾通过 AlgorithmCourses.md 组件引入了三门推荐课程，该文件同样被仓库内所有算法主题页复用：

1. AlgoMonster：主打用数据驱动的方式讲授最高效的题型模式，一次付费终身访问；
2. Grokking the Coding Interview: Patterns for Coding Questions（Design Gurus）：从“题目模式”而非“单题”的角度组织练习，支持 Java、Python、C++、JavaScript 多语言练习与逐步可视化，原文档作者明确表示认同这种按模式学习的方式；
3. Master the Coding Interview: Data Structures + Algorithms（Udemy）：除编码面试外还覆盖简历、非技术面试与薪资谈判的一站式课程，编码演示使用 JavaScript。

结合仓库内各算法速查页的组织方式，一个务实的备考顺序是：先用 字符串速查页 中的两张时间复杂度表和三大技巧建立框架，确认面试澄清问题（字符集、大小写）与边角情况清单，再按“Essential → Recommended”两档刷题，遇到 Rabin-Karp、Trie 这类算法时直接查阅 experimental/utilities 目录下的参考实现对照自己的思路，最后回到 学习资源总表 安排整体复习节奏。