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
AandBwill be between 1 and 10000.The Idea: The constraint is that A must contain all the letters for B. In other words A must be a subset of B. See how many times A fits into B, and then add A to itself this amount of times. This ensures that A is as least as large as B, which for starters, must at least be the minimum amount, because B must be contained in A. If B is not contained in this string, check the next addition of A.
Complexity: O(|B|) time and space
import math
import copy
class Solution:
def repeatedStringMatch(self, A, B):
"""
:type A: str
:type B: str
:rtype: int
"""
A_cp = copy.deepcopy(A)
n_fit = math.ceil(len(B) / len(A))
A *= n_fit
if B in A: return n_fit
A += A_cp
if B in A: return n_fit + 1
return -1
obj = Solution()
print(obj.repeatedStringMatch('abababaaba', 'aabaaba')) # 2
print(obj.repeatedStringMatch('abcd', 'cdab')) # 2
print(obj.repeatedStringMatch('abcd', 'cdabcdab')) # 3
Last modified 4yr ago