Repeated String Match

https://leetcode.com/problems/repeated-string-match/description/

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").

Thoughts

如果B存在于由A组成的str中, 那么B应当是与A中第一个字符和之后的字符匹配, 或第二个字符开始的字符串匹配, 或第N个字符开始匹配. 即0, 1, ..., A.len - 1. 举个例子, A = abcd, B可以与分别以a, b, c, d为开头的拼接出来的字符串相匹配. 所以d和d后面应该能凑够至少与B等长字符串. 最终长度不超过A.len + B.len. 因为如果不与abcd为开头且长度为B的字符串匹配, 后面再贴无论多少, 也只是这些字符串的重复, 依然不会匹配.

Code

class Solution {
    public int repeatedStringMatch(String A, String B) {
        StringBuilder sb = new StringBuilder(A);
        int i = 1;
        while (sb.length() < B.length() || !sb.toString().contains(B)) {
            if(sb.length() - A.length() > B.length()){
                return -1;
            }
            sb.append(A);
            i++;
        }

        return i;
    }
}

Analysis

时间复杂度O(M/N * N + MN) = O(MN).