# 用于编码面试的字符串 cheatsheet

> 原文:[https://www.techinterviewhandbook.org/algorithms/string/](https://www.techinterviewhandbook.org/algorithms/string/)

<header>

## 简介[](#introduction "Direct link to heading")

字符串是一系列字符。许多适用于数组的技巧也适用于字符串。建议您在阅读本页之前阅读关于[阵列](/algorithms/array/)的页面。

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

*   [Trie/前缀树](https://en.wikipedia.org/wiki/Trie)
*   [后缀树](https://en.wikipedia.org/wiki/Suffix_tree)

常见的字符串算法:

*   [Rabin Karp](https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm) 使用滚动散列高效搜索子串
*   [KMP](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm) 用于高效搜索子串

## 时间复杂度[](#time-complexity "Direct link to heading")

字符串是一个字符数组，因此基本字符串操作的时间复杂度与数组操作非常相似。

| 操作 | 大 O |
| --- | --- |
| 接近 | O(1) |
| 搜索 | O(n) |
| 插入 | O(n) |
| 去除 | O(n) |

### 涉及另一串[的操作](#operations-involving-another-string "Direct link to heading")

这里我们假设另一根弦的长度是 m。

| 操作 | 大 O | 注意 |
| --- | --- | --- |
| 查找子字符串 | o(牛米) | 这是最幼稚的情况。还有更有效的字符串搜索算法，如 [KMP 算法](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm) |
| 串联字符串 | O(n + m) |  |
| 薄片 | O(m) |  |
| 拆分(按令牌) | O(n + m) |  |
| 条带(删除前导和尾随空格) | O(n) |  |

## 面试时要注意的事情[](#things-to-look-out-for-during-interviews "Direct link to heading")

询问输入字符集和区分大小写。通常字符限于小写拉丁字符，例如 a 到 z。

## 拐角情况[](#corner-cases "Direct link to heading")

*   空字符串
*   包含 1 或 2 个字符的字符串
*   具有重复字符的字符串
*   只有不同字符的字符串

## 技巧[](#techniques "Direct link to heading")

许多字符串问题属于这些桶之一。

### 计数字符[](#counting-characters "Direct link to heading")

通常你需要计算字符串中字符的出现频率。最常见的方法是使用您选择的语言中的哈希表/映射。如果你的语言有一个内置的计数器类，比如 Python，问问你是否可以用它来代替。

如果需要保存一个字符的计数器，一个常见的错误就是说计数器需要的空间复杂度是 O(n)。一串拉丁字符的计数器所需的空间是 O(1)而不是 O(n)。这是因为上限是字符的范围，通常是 26 个固定常数。输入集只是小写拉丁字符。

#### 唯一字符串[](#string-of-unique-characters "Direct link to heading")

计算一串唯一字符中的字符数的一个巧妙方法是使用一个 26 位的位掩码来表示该字符串中有哪些小写拉丁字符。

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

要确定两个字符串是否有共同的字符，对两个位掩码执行`&`。如果结果非零，即。`mask_a & mask_b > 0`，那么这两个字符串有共同的字符。

### 变位词[](#anagram "Direct link to heading")

变位词是单词转换或单词游戏。它是重新排列一个单词或短语的字母以产生一个新单词或短语的结果，而所有原始字母只使用一次。在面试中，通常我们只会被没有空格的单词困扰。

有几种方法可以确定两个字符串是否是变位词:

*   对两个字符串进行排序应该会产生相同的结果字符串。这需要 O(n.log(n))的时间和 O(log(n))的空间。
*   如果我们将每个字符映射到一个质数，并将每个映射的数相乘，字谜应该有相同的倍数(质因数分解)。这需要 O(n)时间和 O(1)空间。例子:[分组变位](https://leetcode.com/problems/group-anagrams/)
*   字符的频率计数将有助于确定两个字符串是否是字谜。这也需要 O(n)的时间和 O(1)的空间。

### 回文[](#palindrome "Direct link to heading")

回文是一个单词、短语、数字或其他向前和向后读起来一样的字符序列，例如`madam`或`racecar`。

以下是判断字符串是否为回文的几种方法:

*   把字符串反过来，它应该等于它自己。
*   在字符串的开头和结尾有两个指针。向内移动指针，直到它们相遇。在每个时间点，两个指针上的字符都应该匹配。

字符串中字符的顺序很重要，所以哈希表通常没有帮助。

当一个问题是关于计算回文的数目时，一个常见的技巧是让两个指针向外移动，远离中间。注意回文长度可以是偶数也可以是奇数。对于每个中间枢纽位置，您需要检查两次——一次包含字符，一次不包含字符。这种技术用在最长的回文子串中。

*   对于子字符串，一旦没有匹配项，就可以提前终止
*   对于子问题，使用动态规划，因为有重叠的子问题。看看这个问题

## 基本问题[](#essential-questions "Direct link to heading")

如果你在学习这个话题，这些是需要练习的基本问题。

*   [有效的字谜](https://leetcode.com/problems/valid-anagram)
*   [有效回文](https://leetcode.com/problems/valid-palindrome/)
*   [没有重复字符的最长子串](https://leetcode.com/problems/longest-substring-without-repeating-characters/)

## 推荐练习题[](#recommended-practice-questions "Direct link to heading")

*这些是在你为题目学习并练习了基本问题后推荐练习的问题。*

*   [最长重复字符替换](https://leetcode.com/problems/longest-repeating-character-replacement/)
*   [找出一个字符串中的所有变位词](https://leetcode.com/problems/find-all-anagrams-in-a-string)
*   [最小窗口子串](https://leetcode.com/problems/minimum-window-substring/description/)
*   [分组字谜](https://leetcode.com/problems/group-anagrams/)
*   [最长回文子串](https://leetcode.com/problems/longest-palindromic-substring/)
*   [编码和解码字符串(LeetCode Premium)](https://leetcode.com/problems/encode-and-decode-strings/)

## 推荐课程[](#recommended-courses "Direct link to heading")

### [AlgoMonster](https://shareasale.com/r.cfm?b=1873647&u=3114753&m=114505&urllink=&afftrack=)[T3】](#algomonster "Direct link to heading")

AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式，并有内容帮助你快速修改基本的数据结构和算法。最重要的是，AlgoMonster 不是基于订阅的——支付一次性费用，就可以获得**终身访问**。 [**今天加入七折优惠→**](https://shareasale.com/r.cfm?b=1873647&u=3114753&m=114505&urllink=&afftrack=)

### [寻找编码面试:编码问题的模式](https://designgurus.org/link/kJSIoU?url=https%3A%2F%2Fdesigngurus.org%2Fcourse%3Fcourseid%3Dgrokking-the-coding-interview)[](#grokking-the-coding-interview-patterns-for-coding-questions "Direct link to heading")

设计大师的这门课程扩展了推荐练习题中的问题，但从问题模式的角度来进行练习，这是一种我也同意的学习方法，我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题，并提供这些语言的示例解决方案以及一步一步的可视化。**学习和理解模式，而不是背答案！** [**现在获得终身使用权→**](https://designgurus.org/link/kJSIoU?url=https%3A%2F%2Fdesigngurus.org%2Fcourse%3Fcourseid%3Dgrokking-the-coding-interview)

### [掌握编码面试:数据结构+算法](https://fxo.co/DQpY)[](#master-the-coding-interview-data-structures--algorithms "Direct link to heading")

这本 Udemy 畅销书是评分最高的面试准备课程之一(4.6 星，21.5k 评分，135k 学生)，包含了价值 **19 个小时**的内容。像技术面试手册一样，它超越了编码面试，涵盖了简历，非技术面试，谈判。是一个全包！请注意，JavaScript 用于编码演示。 [**结账→**](https://fxo.co/DQpY)

</header>