Python 82ms with optimized concatenation

  • 0

    We can observe that a valid (as in is a substring of A * x) B string is in the form of following:

    [S] + A * x + [P]

    where S and P indicate optional suffix or prefix of A at the beginning and end respectively.

    We can conclude that if A is not in B then a valid B would look like:

    [S] + [P] => S + P or S or P

    Thus if A is not in B we only need to check if B is in A (checks S or P) or A * 2 (checks S + P)

    If A is in B then our valid string looks like such as mentioned above:

    [S] + A * x + [P]

    Thus we can find the first occurrence of A then use that to find the potential end of A * x then add to the count if we have tails on either end.

    After obtaining the count through this logic we can return the count if A is in B.

        def repeatedStringMatch(self, A, B):
            if not B: return 0
            if A not in B: # either S + P or S or P
                return B in A and 1 or (B in A * 2 and 2 or -1)
            start = B.index(A)
            cnt = (len(B) - start) // len(A)
            end = start + cnt * len(A)
            cnt += (start != 0) + (end != len(B))
            return B in A * cnt and cnt or -1

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.