686. Repeated String Match

2017-10-03  本文已影响0人  冷殇弦

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.


class Solution {
    public int repeatedStringMatch(String A, String B) {
        int ans = 0;
        int i=0,j=0;
        while(i<B.length()){
            while(j<A.length()&&i<B.length()){
                if(A.charAt(j)==B.charAt(i)){
                    //System.out.println(i+", "+j);
                    i++;
                    j++;
                }else if(ans==0){
                    //stuck here for test cases
                    i=0;
                    j++;
                }else{
                    //System.out.println(i+", "+j);
                    return -1;
                }
            }
            ans++;
            j = 0;
            //i++;
        }
        return ans;
    }
}
上一篇 下一篇

猜你喜欢

热点阅读