Algorithms study cheatsheets

Coding interview 的 String cheatsheet

String 学习指南，包含练习题、技巧、时间复杂度与推荐资源

Introduction

String 是字符序列。很多适用于 array 的技巧也适用于 string。建议先读 Arrays。

常见的 string lookup 数据结构：

常见 string 算法：

Rabin Karp 用 rolling hash 高效查 substring
KMP 高效查 substring

Time complexity

String 本质上是字符数组，所以基础操作的复杂度接近 array。

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

与另一个 string 的操作

假设另一个 string 长度为 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)

面试时要注意

问清输入字符集和大小写敏感性。通常字符集是小写字母 a-z。

Corner cases

Empty string
只有 1 或 2 个字符
字符重复
全部字符都不重复

Techniques

很多 string 题都落在下面这些类别中：

Counting characters

经常需要统计字符频率。常用方法是 hash table/map。如果语言有内置 Counter（如 Python），可以问是否允许用。

注意一个常见错误：有些人会说计数器的空间复杂度是 O(n)。但如果字符集是固定大小（如 26 个小写字母），空间其实是 O(1) 而不是 O(n)。

Unique characters 的 string

一个小技巧：用 26-bit bitmask 表示字符串里是否包含某个字符。

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

判断两个 string 是否有公共字符：mask_a & mask_b > 0 即有交集。

Anagram

Anagram 指重新排列字母得到新词，且每个字母只用一次（通常不考虑空格）。

判断两个 string 是否 anagram 的方法：

排序后相等。时间 O(n.log(n))，空间 O(n)。
将字符映射到质数并相乘，anagram 会得到相同乘积（质因数分解相同）。时间 O(n)、空间 O(1)。Examples: Group Anagram
统计字符频率并比较。时间 O(n)、空间 O(1)。

Palindrome

Palindrome 是正反读一致的字符串，例如 madam、racecar。

判断 palindrome 的方法：

reverse string 比较
双指针从两端向中间移动，每一步字符相同

由于字符顺序重要，hash table 通常无用。

如果题目是“统计 palindrome 数量”，常用技巧是从中心向外扩展。注意 palindrome 有奇偶长度：每个中心点要检查两次——一次包含中心字符，一次不包含。Examples: Longest Palindromic Substring

Substring：一旦不匹配可提前终止
Subsequence：用 DP 处理重叠子问题。参考 Longest Palindromic Subsequence

Essential questions

该 topic 必练题。