Introduction

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

常见的 string lookup 数据结构：

常见 string 算法：

Time complexity

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

假设另一个 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。

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

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

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

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

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

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

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

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

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

判断 palindrome 的方法：

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

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

该 topic 必练题。

在掌握基础后推荐练习。