力扣刷题笔记 #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 |
|
金典 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 |
|
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,每个状态可以转移给同一对角线的下一个状态,状态转移方程如下: