字符串是一串字符组成的序列，跟数组类似，处理数组的一些方法同样适用于字符串，建议读本文前先读一下 面试中需要熟知的数组知识。
查找字符串常用的数据结构有：
- 前缀树
- 后缀树
常用的字符串算法：
- KMP算法，在字符串匹配时特别高效。
字符串实际上就是一个字符数组，字符串操作和数组操作类似，所以复杂度也基本类似。
| 操作 | 时间复杂度 |
|---|---|
| 访问 | O(1) |
| 搜索 | O(n) |
| 插入 | O(n) |
| 删除 | O(n) |
| 操作 | 时间复杂度 | 备注 |
|---|---|---|
| 查找子串 | O(nm) | 朴素的查找方式 |
| 字符串拼接 | O(n+m) | |
| 字符串切片 | O(m) | |
| 字符串分割(根据指定字符) | O(n+m) | |
| 去除字符串首尾空格 | O(n) |
需要明确字符串是否对大小写敏感，是否只包含英文字符。
- 空字符串。
- 字符串只包含一个或两个字符。
- 字符串包含重复字符。
- 字符串由非重复字符组成。
统计字符串中字符出现的频率，最常见的方法是使用哈希表。有些语言内置了统计函数，比如Python，也可以直接使用。
如果需要进行字符统计，常见的错误是认为统计需要的空间复杂度为 O(n)。统计由小写母组成的字符串需要的空间复杂度是 O(1) 而不是 O(n)。这是因为小写的英文字母只有26个，26是一个常数。
可以通过26位掩码来表示字符串中包含哪些小写字母。
mask = 0
for c in word:
mask |= (1 << (ord(c) - ord('a')))
如果要判断两个字符串中是否包含相同的字符，可以把两个字符串对应的26位掩码做与操作mask_a & mask_b，如果结果不为0，则说明两个字符串中包含相同的字符。
相同字母异位词是一种文字转换或文字游戏。它是重新排列单词或短语的字母以产生新的单词或短语，并且只使用一次所有原始字母。
要确定两个字符串是否为相同字母异位词，有几种方法:
-
对两个字符串排序会得到相同的两个字符串。整个过程需要 O(nlogn) 的时间复杂度和 O(log(n)) 的空间复杂度。
-
素数映射，如果我们将每个字符映射到一个素数，并将映射后的数字相乘，那么相同字母异位词会得到相同的乘积(素数因子分解)。这需要 O(n) 的时间复杂度和 O(1) 的空间复杂度。
-
字符的频率统计也可以用来确定两个字符串是否为相同字母异位词。这同样需要 O(n) 的时间复杂度和 O(1) 的空间复杂度。
回文串是一个字符串序列，从前往后读和从后往前读得到的结果是一致的，如mom或racecar。
下面是判断字符串是否是回文串的方法:
-
把字符串进行翻转，翻转后的字符串和翻转前的字符串保持一致，则说明这个字符串是回文串。
-
在字符串的开始和结束处设置两个指针。将指针同时向中间移动直到它们重合，两个指针指向的字符始终保持一致，那么这个字符串就是回文串。
回文串中字符的顺序很重要，所以判断回文串的时候哈希表通常不适用。
计算字符串回文子串的数量时，常见的方法是中心扩散法，以字符串中的每个字符为中心，使用两个指针由中心向两边移动。回文串可以是偶数或奇数长度。对于回文串的中心位置，需要考虑中心包含两个字符和中心包含一个字符的情况。
- 对于子字符串，一旦没有匹配，就可以提前终止。
- 对于子序列，通常使用动态规划，因为会有重叠的子问题。