Given two strings a
and b
, return the minimum number of times you should repeat string a
so that string b
is a substring of it. If it is impossible for b
to be a substring of a
after repeating it, return -1
.
Notice: string "abc"
repeated 0 times is ""
, repeated 1 time is "abc"
and repeated 2 times is "abcabc"
.
Example 1:
Input: a = "abcd", b = "cdabcdab" Output: 3 Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.
Example 2:
Input: a = "a", b = "aa" Output: 2
Example 3:
Input: a = "a", b = "a" Output: 1
Example 4:
Input: a = "abc", b = "wxyz" Output: -1
Constraints:
1 <= a.length <= 104
1 <= b.length <= 104
a
andb
consist of lower-case English letters.
A:
就是重复,然后再查看。最多做string match 2次
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 nA = A.length(), nB = B.length(); string ss = ""; int res = 0; while(ss.length()<= nB + nA){ ss += A; res++; if(ss.length() >= nB && (ss.find(B) != string::npos)) return res; } return -1; } }; |
No comments:
Post a Comment