引言
字符串是一系列字符的序列。许多适用于数组的技巧也适用于字符串。在阅读本页之前，建议阅读关于数组的页面。
查找字符串的常见数据结构：
常见的字符串算法：
时间复杂度
字符串是字符的数组，因此基本字符串操作的时间复杂度将与数组操作相似。
| 操作 | 大O表示 |
|---|---|
| 访问 | O(1) |
| 搜索 | O(n) |
| 插入 | O(n) |
| 删除 | O(n) |
涉及另一个字符串的操作
这里我们假设另一个字符串的长度为 m。
| 操作 | 大O表示 | 注意 |
|---|---|---|
| 查找子字符串 | O(n.m) | 这是最简单的情况。字符串搜索更有效的算法，如KMP算法 |
| 连接字符串 | O(n + m) | |
| 切片 | O(m) | |
| 分割（按标记） | O(n + m) | |
| 去除前后空格 | O(n) |
面试时需要注意的事项
询问输入字符集和大小写敏感性。通常字符限制为小写拉丁字符，例如a到z。
误区
- 空字符串
- 只有1个或2个字符的字符串
- 有重复字符的字符串
- 只有不同字符的字符串
技巧
许多字符串问题可以分为这些类别。
计数字符
通常需要计算字符串中字符的频率。最常见的方法是在所选语言中使用哈希表/映射。如果你的编程语言有内置的Counter类，如Python，请询问是否可以使用它代替。
如果你需要跟踪字符计数器，一个常见的错误是声称计数器所需的空间复杂度为O(n)。字符串的计数器的空间复杂度实际上是O(1)，而不是O(n)。这是因为上限是字符的范围，通常是固定的常量26。输入集仅为小写拉丁字符。
只含唯一字符的字符串
计算只含唯一字符的字符串中的字符数量的一个巧妙技巧是使用一个26位掩码来指示字符串中哪些小写拉丁字符在其中。
mask = 0
for c in word:
mask |= (1 << (ord(c) - ord('a')))
要确定两个字符串是否有公共字符，对两个掩码执行&操作。如果结果非零，即mask_a & mask_b > 0，则两个字符串有公共字符。
变位词
变位词是指单词或短语的字母重新排列产生新单词或短语的结果，同时仅使用所有原始字母一次。在面试中，通常我们只关心没有空格的单词。
要确定两个字符串是否是变位词，有几种方法：
- 对两个字符串进行排序应该会产生相同的字符串。这需要O(n.log(n))时间和O(log(n))空间。
- 如果我们将每个字符映射到一个质数，并将每个映射的数字相乘，变位词应该有相同的乘积（质因数分解）。这需要O(n)时间和O(1)空间。示例：组变位词
- 字符字符的频率计数将有助于确定两个字符串是否是变位词。这也需要O(n)时间和O(1)空间。
回文
回文是指正读反读都一样的单词、短语、数字或其他字符序列，例如madam或racecar。
以下是一些判断字符串是否为回文的方法：
- 将字符串反转，它应该与自身相等。
- 在字符串的开头和结尾放置两个指针。向内移动指针，直到它们相遇。在任何时候，两个指针处的字符都应该匹配。
字符串内的字符顺序很重要，所以哈希表通常无助于此。
当问题是关于计算回文的数量时，一个常见的技巧是有两个指针向外移动，远离中间。请注意，回文可以是奇数长度或偶数长度。对于每个中间基准位置，你需要检查两次——一次包括字符，一次不包括字符。这种技术在最长回文子串中使用。
- 对于子字符串，一旦没有匹配就终止早期
- 对于子序列，使用动态规划，因为存在重叠子问题。查看这个问题
必需问题
如果你正在为这个主题学习，这是必需练习的问题。
练习题推荐
在你已经为该主题学习和练习了基本问题后，请练习以下推荐题目。
推荐课程
import AlgorithmCourses from '../_courses/AlgorithmCourses.md'