[Leetcode][686. 重复叠加字符串匹配] 3种方法：暴力，字符串哈希，KMP算法
By Long Luo
Leetcode 686. 重复叠加字符串匹配 题目如下：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
27686. 重复叠加字符串匹配
给定两个字符串a和b，寻找重复叠加字符串a的最小次数，使得字符串b成为叠加后的字符串a的子串，如果不存在则返回-1。
注意：字符串"abc"重复叠加0次是""，重复叠加1次是"abc"，重复叠加2次是"abcabc"。
示例 1：
输入：a = "abcd", b = "cdabcdab"
输出：3
解释：a 重复叠加三遍后为"ab**cdabcdab**cd", 此时b是其子串。
示例 2：
输入：a = "a", b = "aa"
输出：2
示例 3：
输入：a = "a", b = "a"
输出：1
示例 4：
输入：a = "abc", b = "wxyz"
输出：-1
提示：
1 <= a.length <= 10^4
1 <= b.length <= 10^4
a 和 b 由小写英文字母组成
分析
可以分为下面\(3\)种情况：
\(\textit{A}\) ==\(\textit{B}\)，复制 \(1\) 次；
\(lenA > lenB\)，直觉是只需要复制 \(2\) 次；
\(lenA < lenB\)，首先至少将 \(\textit{A}\) 复制几次后长度 \(>=lenB\)，然后至多再复制 \(\textit{A}\) 一次。
下面简单证明下，也就是复制次数的下限和上限：
至少将字符串 \(\textit{A}\) 复制 \(N\) 次之后主串 \(\textit{S}\)，那么 \(lenS >= lenB\) ，才有可能匹配，至此我们得到了复制次数的下限：\(\frac{lenB}{lenA}+1\)；
如果从主串 \(\textit{S}\) 中找到子串 \(\textit{B}\)，因此可以明确子串的起始位置，不会超过 \(lenA\)；因为如果起始匹配位置 \(>= lenA\)，那么说明在之前已经被匹配过了。
综上分析可知：
\[ \frac{lenB}{lenA} + 1 \le repeatedTimes \le \frac{lenB}{lenA} + 2 \]
方法一：暴力
思路与算法：
首先想到的是暴力法。最开始没有去分析复制次数上下限时，使用了一个朴素的想法：
- \(\textit{B}\) 中含有 \(\textit{A}\) 中没有的字母，那么直接返回 \(-1\)；
- 最少复制次数：\(\textit{B}\) 中字母出现次数 \(\textit{A}\) 中字母次数的最大值。
使用 \(\texttt{HashMap}\) 存储字母出现次数。
代码如下所示：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
34public int repeatedStringMatch(String a, String b) {
if (a.equals(b) || a.contains(b)) {
return 1;
}
int min = 1;
Map<Character, Integer> mapA = new HashMap<>();
Map<Character, Integer> mapB = new HashMap<>();
for (char ch : a.toCharArray()) {
mapA.put(ch, mapA.getOrDefault(ch, 0) + 1);
}
for (char ch : b.toCharArray()) {
mapB.put(ch, mapB.getOrDefault(ch, 0) + 1);
}
for (char ch : mapB.keySet()) {
if (!mapA.containsKey(ch)) {
return -1;
} else {
int times = mapB.get(ch) / mapA.get(ch);
min = Math.max(min, times);
}
}
StringBuilder res = new StringBuilder(a);
for (int i = 2; i <= min + 1; i++) {
res.append(a);
if (res.toString().contains(b)) {
return i;
}
}
return -1;
}
因为字符串均由小写英文字母组成，所以可以直接用数组进行计数，速度提高了很多。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
38public int repeatedStringMatch(String a, String b) {
if (a.equals(b) || a.contains(b)) {
return 1;
}
int[] cntA = new int[26];
int[] cntB = new int[26];
for (char ch : a.toCharArray()) {
cntA[ch - 'a']++;
}
for (char ch : b.toCharArray()) {
cntB[ch - 'a']++;
}
int min = 1;
for (int i = 0; i < 26; i++) {
if (cntB[i] > 0 && cntA[i] == 0) {
return -1;
}
if (cntA[i] > 0) {
int times = cntB[i] / cntA[i];
min = Math.max(min, times);
}
}
StringBuilder res = new StringBuilder(a);
for (int i = 2; i <= min + 1; i++) {
res.append(a);
if (res.toString().contains(b)) {
return i;
}
}
return -1;
}
值得一提的是，如果不用比较 \(\textit{A}\), \(\textit{B}\) 字母的话，直接进行比较的话，那么耗时会成倍增加，所以预先排除一些test case有很大帮助。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17public int repeatedStringMatch(String a, String b) {
if (a.equals(b) || a.contains(b)) {
return 1;
}
int minRepeatTimes = Math.max(1, b.length() / a.length() + 1);
StringBuilder res = new StringBuilder(a);
for (int i = 2; i <= minRepeatTimes + 1; i++) {
res.append(a);
if (res.toString().contains(b)) {
return i;
}
}
return -1;
}
复杂度分析：
- 时间复杂度：\(O(n + m + nm)\)，其中 \(n\) 为 \(\textit{A}\) 的长度，\(m\) 为 \(\textit{B}\) 的长度。
- 空间复杂度：\(O(26)\)。