Leetcode——686. 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”).

Note:

The length of

A

and

B

will be between 1 and 10000.

題目解析

這個題還是很簡單的，題目要求就是想要得到A字元串經過一次一次的追加本身，是否追加的結果中包含字元串B。因為想到追加字元串，第一個想到的就是StringBuilder類，因為有append方法呀。題目最後想要傳回追加的次數，如果不管追加幾次最後字元串B都不是A的子串，則傳回-1，否則傳回次數。是以思路就是每次追加都用變量count自加一次。

那什麼時候回出現不管追加幾次都不符合題意呢？我覺得就是當初始的時候字元串A長度大于B，并且在追加A之後，不滿足字元串B是A的子串就會不滿足題意。

AC代碼

class Solution {
    public int repeatedStringMatch(String A, String B) {
        StringBuilder sb = new StringBuilder(A);
        int count = 1;
        while(sb.indexOf(B) < 0) {
            if(sb.length() - A.length() > B.length())
                return -1;
            sb.append(A);
            count ++;

        }
        return count;
    }
}