【题目】
给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数,使得字符串B成为叠加后的字符串A的子串,如果不存在则返回 -1。
举例,A = "abcd",B = "cdabcdab"。
答案为 3, 因为 A 重复叠加三遍后为 “abcdabcdabcd”,此时 B 是其子串;A 重复叠加两遍后为"abcdabcd",B 并不是其子串。
注意:
A 与 B 字符串的长度在1和10000区间范围内。
【思路】
将A重复n次后记为C,那么要使得B是C的子串,必须len(B) <= len(C)。
因此,至少重复len(B) // len(A)次。(python的//表示相除后向下取整)
那么至多重复多少次呢?
len(B) // len(A) + 2次。(提示,B的首字符为A的尾字符,B的尾字符为A的首字符,这样,恰好多了2次。
【代码】
python版本
class Solution(object):
def repeatedStringMatch(self, A, B):
"""
:type A: str
:type B: str
:rtype: int
"""
count = len(B) // len(A)
tmp = A * count
if tmp.find(B) > -1:
return count
else:
tmp += A
if tmp.find(B) > -1:
return count +
else:
tmp += A
if tmp.find(B) > -1:
return count +
return -1
C++版本
class Solution {
public:
int repeatedStringMatch(string A, string B) {
int count = B.size() / A.size();
string tmp = "";
for(int i=; i<count; i++)
tmp += A;
if(tmp.find(B) != -1)
return count;
else{
tmp += A;
if(tmp.find(B) != -1)
return count + ;
else{
tmp += A;
if(tmp.find(B) != -1)
return count + ;
return -1;
}
}
}
};