686. 重复叠加字符串匹配

亦凉 2022-10-16 09:59 113阅读 0赞

> 给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。
> 
> 注意：字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。
> 
> 示例 1：
> 
> 输入：a = "abcd", b = "cdabcdab"  
> 输出：3  
> 解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。  
> 示例 2：
> 
> 输入：a = "a", b = "aa"  
> 输出：2  
> 示例 3：
> 
> 输入：a = "a", b = "a"  
> 输出：1
> 
>

class Solution {
        public int repeatedStringMatch(String a, String b) {
            /**  
            
            如果A的长度小于B的长度，这时B是A的重复子串，则A的重复次数不超过 Bsize / Asize + 2。
             A*q或者 A*(q+1)  或者A*(q+2)。  --> q>=len(B)/len(A)
             */
    
                int q=b.length()/a.length();
                StringBuilder sb=new StringBuilder();//拼接用
                int count=q;//循环用
                while(count>0){
                    sb.append(a);  
                    count--;
                }
    
                //看下是否属于sb的子串
                if(sb.toString().indexOf(b)!=-1){
                    //属于
                    return q;
                }
    
                //如果不属于在拼接一次a
                sb.append(a);
                if(sb.toString().indexOf(b)!=-1){
                     //属于
                     return q+1;
                }
                sb.append(a);
                if(sb.toString().indexOf(b)!=-1){
                     //属于
                     return q+2;
                }
    
                //都没找到 说明找不到了 返回-1
                return -1;
        }
    }