力扣刷题笔记 #12 字符串

本文最后更新于：2023年3月22日 晚上

本文包含「字符串」类型题中的：打印输出、KMP 算法、Trie 树、字符串哈希等。持续更新中。

题目描述：

方法1：

方法2：

方法3：

坑点：

打印输出

面试常考的一类题，利用简单的技巧将繁琐的输出简化，考验思维。

9. 回文数 (E)

题目描述：给你一个整数 x，判断 x 是否为一个回文整数。

方法1：逐位分解，先特判数字 $0$ 和 $10$ 的倍数，然后从末位开始取出数字，同时放到一个临时变量中判断。

方法2：整数转字符串，将原数字用 to_string 和 reverse 翻转，再和原数字比较。

坑点：方法 2 和原数字比较时，应该把两个数都转为字符串，如果将翻转后的数 stoi 则可能会溢出！

7. 整数反转 (M)

题目描述：给你一个 32 位的有符号整数，返回将数字反转后的结果，如果反转后超过 INT 的取值则返回 0。

方法：利用一个 64 位整数暂存，取出负号最后处理，最后结果判断先是否在范围内再返回。

坑点：负号也可以无需处理，负数对正数的除法和取模运算会保留负号，但是不同语言、机器的特性不同，可能会出错，因此最好取出负号单独处理！

6. Z 字形变换 (M)

题目描述：给定字符串 s 和行数 r，以从上往下、从左到右进行 Z 字形排列，再从左往右逐行读取，产生出一个新的字符串。

方法1：二维矩阵模拟，遍历字符串并按 Z 字形填写矩阵，再逐行输出，时空复杂度均为 $O(r \times n)$。

方法2：按行模拟，创建 $r$ 个空字符串，遍历 s 并折返写入每行（用一个方向标记即可），时空复杂度 $O(n)$。

方法3：直接构造，每个周期有 $t=2r-2$ 个字符，通过模 $t$ 取余可以枚举每一行的下一个字符。第一行和最后一行的余数为 $0$ 和 $r-1$，中间第 $i$ 行每周期内有两个字符，余数分别是 $i$ 和 $t-i$。空间复杂度 $O(1)$。

48. 旋转图像 (M)

题目描述：给定一个 $n\times n$ 的二维矩阵表示图像，将其顺时针旋转 90 度，要求原地操作。

方法1：转置 + 翻转，先沿着对角线转置，再进行水平翻转，空间复杂度 $O(1)$。

方法2：直接交换，矩阵中对应的四个点为一组，用一个 $temp$ 变量就能完成四个点的旋转。当 $n$ 为偶数的分组显而易见；为奇数时正中央的点无需旋转，四个角各有一个矩形。空间复杂度 $O(1)$。

KMP

BF 暴力算法：

  • 从主串 S 的第一个字符起，与模式 T 的第一个字符比较，若相等，则继续逐个比较后续字符；否则从 S 的下一个字符起，重新和 T 的字符比较。此时的 T 每次失败都要完全回溯。
  • 最坏时间复杂度为 $O(nm)$，其中 $n$ 和 $m$​ 分别为主串和模式串的长度。例如，当模式串为 00001，而主串为 000000000000000000000000001 时，每趟匹配都是比较到模式的最后一个字符时才发现不等，产生大量不必要的回溯。

KMP 算法：

  • 整个匹配过程中，子串不回溯，通过 next 数组快速前移，$O(n+m)$ 的时间完成串的模式匹配操作。
  • next[j] 的含义是：代表当前字符之前的字符串中，有多大长度的相同前缀后缀（意味着失配的时候，成功匹配过的后缀是可以利用的）。在子串的第 $j$ 个字符与主串发生失配时，则将子串的第 next[j] 位置前移到当前主串失配的位置，重新比较。
  • 如何求 next：动态规划递推求，若 next[j-1]=2，则 next[j] 只要看新的一位是否等于前缀的后一位。注意整个 next 是往后偏移一格的，next[0] 默认置为 -1，因为第一个就失配时子串右移一格。
  • nextVal[j] 的含义：在 next 数组的基础上，如果 next[j] 为 k，就比较模式串的 j 和 k 位，如果相同则置为 -1。

KMP 算法模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int strStr(string s, string p) {
    int n = s.size(), m = p.size();
    if(m == 0) return 0;
    vector<int> next(m);
    // DP 预处理 next 数组
    for(int i = 1, j = 0; i < m; i++){
        while(j > 0 && p[i] != p[j]) j = next[j - 1];
        if(p[i] == p[j]) j++;
        next[i] = j;
    }
    // 匹配过程
    for(int i = 0, j = 0; i < n; i++){
        while(j > 0 && s[i] != p[j]) j = next[j - 1];
        if(s[i] == p[j]) j++;
        if(j == m) return i - m + 1;
    }
    return -1;
}

金典 01.09. 字符串轮转 (E)

题目描述：给定两个字符串s1和s2，检查s2是否为s1轮转而成。

方法1：暴力，把 s2 中的每个字符当作起点匹配 s1，要进行 % n 操作，复杂度 $O(n^2)$。

方法2：拼接法，对于所有环形序列问题，都可以把原序列复制拼接在后面，当成线性序列进行字符串匹配。C++ 的 find 复杂度 $O(n^2)$，手写 KMP 算法复杂度 $O(n)$。

坑点：如果两个字符串长度不一样，则必不可能进行轮转互换，但是用拼接法可能会误判。

459. 重复的子字符串 (E)

题目描述：给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

方法1：枚举，显然子串的长度是总长度的因数，由于子串至少重复一次，只需在 $[1, n/2]$ 范围内枚举长度即可，再取 s 的前缀进行匹配，时间复杂度 $O(n^2)$。

方法2：拼接法，如果一个字符串有重复性质，则原串复制拼接后的 s+s 也具有重复性质，移除 s+s 的第一个和最后一个字符，如果 s 是新字符串的子串，则满足题目要求。时间复杂度 $O(n^2)$。

方法3：拼接法 + KMP，手写 KMP 查找子串，时间复杂度 $O(n)$。

Trie 树

Trie 树是一种 N 叉树（26 叉树）：

  • 每个节点包含一个字符（根节点除外），从根节点到某一节点的路径上的字符代表该节点对应的字符串。
  • 两个有公共前缀的单词，在 Trie 树中前缀部分的路径相同，所以 Trie 树又叫做前缀树（Prefix Tree）。
  • 每个节点的子节点包含的字符各不相同，根节点通往不同字符串的路径唯一。
  • 通常在实现时，会在节点中设置一个标志位，用来标记该节点处是否构成一个单词。

Trie 树可以实现 $O(m)$ 插入、查询字符串，$m$ 是字符串的长度。虽然哈希表的复杂度 $O(1)$ 看起来更快，但是求哈希值也需要遍历字符串，且在字符串过多时可能会大量冲突，时间效率不高。此外 Trie 树还可以对关键字按字典序排序（先序遍历）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Trie {
private:
    Trie* son[26] = {};
    bool isWord = false;
public:
    Trie() {
        isWord = false;
        for(int i = 0; i < 26; i++) son[i] = nullptr;
    }
    
    ~Trie(){
        for(int i = 0; i < 26 ; i++){
            if(son[i] != nullptr) delete son[i];
        }
    }

    void insert(const string& word) {
        Trie* root = this;
        for(const char &x: word){
            int cur = x - 'a';
            if(root->son[cur] == nullptr) root->son[cur] = new Trie();
            root = root->son[cur];
        }
        root->isWord = true;
    }
    
    bool search(const string& word) {
        Trie* root = this;
        for(const char &x : word){
            int cur = x - 'a';
            if(root->son[cur] == nullptr) return false;
            root = root->son[cur];
        }
        return root->isWord;
    }
    
    bool startsWith(const string& prefix) {
        Trie* root = this;
        for(const char &x : prefix){
            int cur = x - 'a';
            if(root->son[cur] == nullptr) return false;
            root = root->son[cur];
        }
        return true;
    }
};

208. 实现 Trie (前缀树) (M)

题目描述：实现 Trie 类，包含初始化、插入、检索字符串、检索前缀。

方法1：二维数组，用一个 $trie[N][26]$ 来存储树节点的子节点下标，$end[N]$ 数组记录树节点是否被当作结尾，一个 $idx$ 变量标记最后一个有值的树节点。此方法开销更小，但需要提前估算大小，适合 ACM 竞赛。

Insert：遍历单词的每个字符，用 p 表示下标，从数组起点 trie[0][x-'a'] 向下寻找子树，当该值为 0 时，到达尽头，需要插入新的节点到 ++idx 下标所在位置，继续扩展树。扩展结束后，置最后一个位置 end[p]=1。

Search：遍历单词的每个字符，当 trie[p][x-'a'] 为 0 时，代表不存在此单词，返回 false；如果遍历结束，直接返回 end[p] 即可知道是否存在。

StartWith：同上，但是遍历结束时，可以直接返回 true。

方法2：动态申请 Trie 节点，Trie 类私有指针数组指向 26 个节点，以及一个 $isWord$ 标志位。在构造函数中将标志位置 false，指针置空。此方法适合面向对象。

Insert：遍历单词的每个字符，用 Trie* 指针遍历节点，遍历到尽头时扩展，需要 new 一个 Trie 节点。扩展结束后，置最后一个节点 isWord 为 true。

Search、StartWith 和方法 1 类似，不再赘述。

2416. 字符串的前缀分数和 (H)

题目描述：给定长度为 n 的数组 words，数组中每个字符串的每个前缀，每出现一次就得一分，返回一个长度为 n 的数组 answer，其中 answer[i] 是 words[i] 的每个非空前缀的分数总和。

方法1：哈希表，第一次遍历每个单词，将每个前缀在哈希表中的分数增一，第二次遍历时累加每个前缀的分数。复杂度 $O(n^3)$，因为 C++ 对字符串进行哈希运算同样需要 $O(Len)$，换成 Python 或 JS 等语言可过。

方法2：Trie，但是不需要 $isWord$ 标志位，只需在每个节点中存储当前前缀的分数，在插入时路径上的分数增一，检索时累加路径上的分数。复杂度 $O(n^2)$。

方法3：字符串单哈希，仍用 C++ 无序映射，但是将键换成 long long，用 x = (x * p + ch) % mod 设置键，其中 p 设置为较大质数防止冲突。复杂度 $O(n^2)$。

字符串哈希

本质是「将匹配两个字符串相等的复杂度由 $O(n)$ 优化到 $O(1)$」，常用的字符串哈希方法：

  • 自然溢出：不定义 $MOD$，开 unsigned long long 自然溢出，默认 $MOD=2^{64}-1$。
  • 单哈希：需要开 long long 取大质数，常用 $Base=31, MOD=1e9+7$。
  • 双哈希：公式同上，用两个 $Base$ 和 $MOD$ 得到二元组，同时比对两个值更安全。

存储单哈希结果可以用一个二维矩阵，$hash[i][j]$ 表示 $s[i\cdots j]$，也可以用一维矩阵存储，再 $O(1)$ 查询，注意防止负数，同时 $Base$ 的幂次也要顺便存储：

尽管可能性很低，但还是可能存在哈希冲突。字符串哈希可以帮助迅速排除绝大多数不相等/元素不存在的情况，对于剩下的情况，如果必须确认两个字符串是否相等，或者元素是否存在于容器内，我们还是要再一次进行完整的查验。

49. 字母异位词分组 (M)

题目描述：给定一些字符串，将其划分为若干组，使得每组中的单词都是字母异位词，即字母相同但顺序不同。

方法1：排序 + 哈希表，将每个字符串内部排序，则所有字母异位词都会变成同一个单词，将其作为哈希的键即可存下所有字母异位词，再将其分组输出。时间复杂度 $O(nk \log k)$。

方法2：计数 + 哈希表，计数的桶用 char 来表示，整个计数表就是一个字符串，作为哈希的键，时间复杂度 $O(nk)$。

方法3：顺序无关字符串哈希，用不同的质数表示 26 个字母，把每个字母的值相乘取模，就能确保字母异位词的乘积必定是相等的，且非字母异位词的乘积不会相等。时间复杂度 $O(nk)$。

2430. 对字母串可执行的最大删除数 (H)

题目描述：给定一个字符串 s，在一步操作中，你可以：删除整个序列；任取 i，如果有 s[:i]==s[i:2*i]，删除 s[:i]。返回删除 s 可能的最大操作数。

方法1：DP + 字符串单哈希，将字符串逆序，$dp[i]$ 表示删除前 $i$ 个字母可能的最大操作数，显然 $dp[0]=0$，答案为 $dp[n-1]$，每次枚举可删除的字母长度 $j$，如果 $s[i-j+1:i]=s[i-2j+1:i-j]$ 则转移，预处理一个二维哈希值矩阵，则可以 $O(1)$ 匹配。复杂度 $O(n^2)$。

方法2：DP + 最长公共前缀 (LCP)，不需要将字符串逆序，从后往前 DP。不用预计算哈希值，而是用先 DP 得到 LCP 结果，$lcp[i][j]$ 表示 s[i:] 和 s[j:] 的最长公共前缀，如果 $lcp[i][i+j]>=j$ 则转移。复杂度 $O(n^2)$。

LCP：$lcp[i][n]$ 和 $lcp[n][j]$ 都是 0，从后往前 DP，每个状态可以转移给同一对角线的下一个状态，状态转移方程如下：

算法笔记 > 力扣刷题
#Algorithm
力扣刷题笔记 #12 字符串
https://hwcoder.top/LeetCode-String
作者
Wei He
发布于
2022年10月2日
许可协议