Saturday, March 2, 2019

Leetcode 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.
Code (Java):
class Solution {
    public int repeatedStringMatch(String A, String B) {
        if (A == null || A.length() == 0) {
            return -1;
        }

        if (B == null || B.length() == 0) {
            return 0;
        }

        // step 1: calculate the min number of steps since lenA >= lenB
        //
        int count = 0;
        StringBuilder sb = new StringBuilder();

        while (sb.length() <= B.length() + A.length()) {
            if (sb.toString().contains(B)) {
                break;
            } else {
                sb.append(A);
                count++;
            }
        }

        if (sb.toString().contains(B)) {
            return count;
        } else {
            return -1;
        }
    }
}

Discussion:
Why we need to check sb().length <= A.length() + B.length()? There is one corner case
A = abc
B = cabcacbc

The expected answer is 4. 

If we just stop when sb.length() > B.length(), we may miss one more step.  

No comments:

Post a Comment