题目描述
给定两个字符串 a
和 b
,寻找重复叠加字符串 a
的最小次数,使得字符串 b
成为叠加后的字符串 a
的子串,如果不存在则返回 -1
。
注意:字符串 "abc"
重复叠加 0 次是 ""
,重复叠加 1 次是 "abc"
,重复叠加 2 次是 "abcabc"
。
示例 1:
输入:a = "abcd", b = "cdabcdab"
输出:3
解释:a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。
示例 2:
输入:a = "a", b = "aa"
输出:2
示例 3:
输入:a = "a", b = "a"
输出:1
示例 4:
输入:a = "abc", b = "wxyz"
输出:-1
提示:
1 <= a.length <= 104
1 <= b.length <= 104
a
和 b
由小写英文字母组成
解法
方法一
| class Solution:
def repeatedStringMatch(self, a: str, b: str) -> int:
m, n = len(a), len(b)
ans = ceil(n / m)
t = [a] * ans
for _ in range(3):
if b in ''.join(t):
return ans
ans += 1
t.append(a)
return -1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution {
public int repeatedStringMatch(String a, String b) {
int m = a.length(), n = b.length();
int ans = (n + m - 1) / m;
StringBuilder t = new StringBuilder(a.repeat(ans));
for (int i = 0; i < 3; ++i) {
if (t.toString().contains(b)) {
return ans;
}
++ans;
t.append(a);
}
return -1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution {
public:
int repeatedStringMatch(string a, string b) {
int m = a.size(), n = b.size();
int ans = (n + m - 1) / m;
string t = "";
for (int i = 0; i < ans; ++i) t += a;
for (int i = 0; i < 3; ++i) {
if (t.find(b) != -1) return ans;
++ans;
t += a;
}
return -1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | func repeatedStringMatch(a string, b string) int {
m, n := len(a), len(b)
ans := (n + m - 1) / m
t := strings.Repeat(a, ans)
for i := 0; i < 3; i++ {
if strings.Contains(t, b) {
return ans
}
ans++
t += a
}
return -1
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | function repeatedStringMatch(a: string, b: string): number {
const m: number = a.length,
n: number = b.length;
let ans: number = Math.ceil(n / m);
let t: string = a.repeat(ans);
for (let i = 0; i < 3; i++) {
if (t.includes(b)) {
return ans;
}
ans++;
t += a;
}
return -1;
}
|