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



results matching ""

    No results matching ""