repeatedStringMatch.java

repeatedStringMatch.java

package leetcode.repeatedStringMatch;

/**
 * Created by siyao on 9/30/17.
 * https://leetcode.com/contest/leetcode-weekly-contest-52/problems/repeated-string-match/
 * Solution:
 * There are just few cases. Then at some point of repeating, if B is still not a substring,
 * then we can just stop. So the key is to find the "point", t and t + 1.
 *
 * Thinking:
 * There of course some logic and math behind. Think about it and simplify the code.
 *
 */
class Solution {
    public int repeatedStringMatch(String A, String B) {
        int la = A.length();
        int lb = B.length();
        if (lb <= la) {
            if (A.contains(B)) {
                return 1;
            } else {
                String AA = times(A, 2);
                if (AA.contains(B)) {
                    return 2;
                } else {
                    return -1;
                }
            }
        }
        int t = lb % la == 0 ? lb / la : lb / la + 1;
        String AA = times(A, t);
        if (AA.contains(B)) {
            return t;
        }
        String AAA = times(A, t + 1);
        if (AAA.contains(B)) {
            return t + 1;
        }
        return -1;
    }

    private String times(String a, int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            sb.append(a);
        }
        return sb.toString();
    }
}
/*
686. Repeated String Match My SubmissionsBack to Contest
User Accepted: 302
User Tried: 703
Total Accepted: 302
Total Submissions: 1389
Difficulty: Easy
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.
 */