第五章 - 高频考题（中等）
1906. 查询差绝对值的最小值
0686. 重复叠加字符串匹配
题目地址(686. 重复叠加字符串匹配)
题目描述
1
给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。
2
3
注意：字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。
4
5
6
7
示例 1：
8
9
输入：a = "abcd", b = "cdabcdab"
10
输出：3
11
解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。
12
示例 2：
13
14
输入：a = "a", b = "aa"
15
输出：2
16
示例 3：
17
18
输入：a = "a", b = "a"
19
输出：1
20
示例 4：
21
22
输入：a = "abc", b = "wxyz"
23
输出：-1
24
25
26
提示：
27
28
1 <= a.length <= 104
29
1 <= b.length <= 104
30
a 和 b 由小写英文字母组成
Copied!
前置知识
- set
公司
- 暂无
思路
首先，一个容易发现的点是如果 b 中包含有 a 中没有的字符， 那么一定需要返回 - 1。因此使用集合存储 a 和 b 的所有字符，并比较 b 是否是 a 的子集，如果不是，则直接返回 - 1。
接着我们逐个尝试：
- 两个 a 是否可以？
- 三个 a 是否可以？
- 。。。
- n 个 a 是否可以？
如果可以，则直接返回 n 即可。关于是否可以的判断， 我们可以使用任何语言自带的 indexof 算法，Python 中 可以使用
b in a 判读 b 时候是 a 的子串。代码:
1
cnt = 1
2
while True:
3
if b in a * cnt:
4
return cnt
5
cnt += 1
6
return -1
Copied!
上面的代码有 BUG，会在一些情况无限循环。比如：
1
a = "abcabcabcabc"
2
b = "abac"
Copied!
因此我们必须设计出口，并返回 -1。问题的我们的上界是什么呢？
这里有个概念叫解空间。这是一个很重要的概念。 我举个简单的例子。 你要在一个数组 A 中找某一个数的索引，题目保证这个数字一定在数组中存在。那么这道题的解空间就是 [0, n -1]，其中 n 为数组长度。你的解不可能在这个范围外。
回到本题，如果 a 经过 n 次可以匹配成功， 那么最终 a 的长度范围是 [len(b), 2 * len(a) + len(b)]。
下界是 len(b) 容易理解， 关键是上界。
假设 a 循环 n 次可以包含 b。那么必定属于以下几种情况中的一种：
循环次数下界为 len(b) + len(a ) - 1 / len(a)
- 1.循环 n 次正好匹配。 比如 a = 'abc', b = 'abcabcabcabcabc'（5 个 abc）。循环 5 次恰好匹配，这五次循环其实就是上面提到到下界
- 2.第 n 次循环恰好匹配，这个时候第 n 次循环的前 k 个字符必定匹配（其中 0 < k <= len(a)），比如 a = 'abc', b = 'abcabcab'。第三次匹配正好匹配，且匹配了 abc 中的前两个字符 ab，也就是说比下界多循环一次。
- 3.再比如： a = "ab", b = "bababa"，那么需要循环 5 次 变成 ababababab（粗体表示匹配 b 的部分），其中 3 次是下界，也就是说比下界多循环了两次。
除此之前没有别的可能。
可以看出实际上 n 不会大于下界次循环 + 2，因此最终 a 的长度的临界值就是 2 * len(a) + len(b)。超过这个范围再多次的叠加也没有意义。
关键点解析
- 答案是有限的， 搞清楚解空间是关键
代码
代码支持: Python
1
class Solution:
2
def repeatedStringMatch(self, a: str, b: str) -> int:
3
if not set(b).issubset(set(a)):
4
return -1
5
cnt = 1
6
while len(a * cnt) < 2 * len(a) + len(b):
7
if b in a * cnt:
8
return cnt
9
cnt += 1
10
return -1
Copied!
复杂度分析
- 时间复杂度：b in a 的时间复杂度为 M + N（取决于内部算法），因此总的时间复杂度为 $O((M + N) ^ 2)$，其中 M 和 N 为 a 和 b 的长度。
- 空间复杂度：由于使用了 set，因此空间复杂度为 $O(M +N)$，其中 M 和 N 为 a 和 b 的长度。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 1yr ago