686. Repeated String Match
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.
Solution
(1) Java
class Solution {
public int repeatedStringMatch(String A, String B) {
if (A == null || A.length() == 0 || B == null || B.length() == 0) {
return -1;
}
int rst = 1;
StringBuilder sb = new StringBuilder(A);
while (sb.length() < B.length()) {
rst++;
sb.append(A);
}
if (sb.indexOf(B) == -1) {
sb.append(A);
rst++;
}
if (sb.indexOf(B) == -1) {
return -1;
}
return rst;
}
}
(2) Python
class Solution:
def repeatedStringMatch(self, A, B):
"""
:type A: str
:type B: str
:rtype: int
"""
def getNext():
i, j = 0, 1
while j < len(B):
if B[i] == B[j]:
next[j] = i+1
i += 1
j += 1
else:
if i == 0:
j += 1
else:
i = next[i-1]
if not A or not B:
return -1
next = [0]*len(B)
getNext()
i,j = 0, 0
while i < len(A):
while j < len(B) and A[int(i+j)%len(A)] == B[j]:
j += 1
if j == len(B):
return math.ceil(float(i+j)/len(A))
if j == 0:
i += 1
else:
i += max(1, j-next[j-1])
j = next[j-1]
return -1
(3) Scala