[leetcode] 686. 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.

分析

• 如果B要能成為A的字元串，那麼A的長度肯定要大于等于B，是以當A的長度小于B的時候，我們可以先進行重複A，直到A的長度大于等于B，并且累計次數cnt。那麼此時我們用find來找，看B是否存在A中，如果存在直接傳回cnt。如果不存在，我們再加上一個A，再來找，這樣可以處理這種情況A=“abc”, B=“cab”，如果此時還找不到，說明無法比對，傳回-1

代碼

class Solution {
public:
    int repeatedStringMatch(string A, string B) {
        int m=A.length();
        int n=B.length();
        int cnt=0;
        string s="";
        int i=0;
        while(i<n){
            i+=m;
            s+=A;
            cnt++;
        }
        if(s.find(B)!=string::npos) return cnt;
        s+=A;
        if(s.find(B)!=string::npos) return cnt+1;
        return -1;
    }
};      

參考文獻