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
The length of
A
and B
will be between 1 and 10000.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