686.Repeated String Match
686.Repeated String Match
难度:Easy
Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.
For example, with A = "abcd" and B = "cdabcdab".
Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").
Note: The length of A and B will be between 1 and 10000.
可以将A循环补至长度大于B,然后判断B是否是增补的A的子集。 最后确定循环的A的次数。
1
class Solution {
2
public:
3
int repeatedStringMatch(string A, string B) {
4
int t= B.size()/A.size()+1;
5
string tmp=A;
6
while(t--)
7
{
8
tmp+=A;
9
}
10
size_t start= tmp.find(B);
11
if(start ==string::npos) return -1;
12
int end=start+B.size()-1;
13
if(end == start) return 1;
14
// cout<<start<<" "<< end << endl;
15
start = start/A.size() *A.size();
16
end = ((end+1)/A.size()+((end+1)%A.size() !=0) ) *A.size();
17
// cout<<start<<" "<< end << endl;
18
return (end-start)/A.size();
19
20
}
21
};
Copied!
执行用时 :12 ms, 在所有 C++ 提交中击败了97.00%的用户 内存消耗 :9.1 MB, 在所有 C++ 提交中击败了82.83%的用户
Copy link