686 Repeated String Match

686. Repeated String Match

1. Question

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 ofAandBwill be between 1 and 10000.

2. Implementation

(1) Brute Force

思路：如果A要包含B的话，那么A的长度必须大于等于B, 所以我们不断重复A，直到它的长度大于等于B。如果A此时包含B，则返回重复A的次数count，如果还不包含，比如A = "abc", B = "cab"这种形式，说明A的长度等于B，但刚好B是A的rotation，所以我们再重复A多一次，然后判断是否含有B. A长度大于B时，仍然不包含B，则返回-1

class Solution {
    public int repeatedStringMatch(String A, String B) {
        int count = 0;

        StringBuilder sb = new StringBuilder();

        while (sb.length() < B.length()) {
            sb.append(A);
            ++count;
        } 

        if (sb.toString().indexOf(B) >= 0) {
            return count;
        }

        if (sb.append(A).toString().indexOf(B) >= 0) {
            return count + 1;
        }
        return -1;
    }
}

3. Time & Space Complexity

Brute Force: 时间复杂度O(m/n), m是B的长度, n是A的长度，空间复杂度O(m)