【leetcode刷题】T88-重复叠加字符串匹配
【题目】
给定两个字符串 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;
}
}
}
};本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-06-11，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读