[Leetcode][第459题][JAVA][重复的字符串][子串][匹配]-蒲公英云

[Leetcode][第459题][JAVA][重复的字符串][子串][匹配]

【问题描述】[中等]

在这里插入图片描述

【解答思路】

1. 枚举

找出能整除的子串长度，再用substring遍历匹配即可
时间复杂度：O(N^2) 空间复杂度：O(1)

class Solution { 
  public boolean repeatedSubstringPattern(String s) { 
        int len = s.length();
        for(int i = 1 ;i<=len/2;i++){ 
            String sub = s.substring(0,i);
            int lenSub = sub.length();
            int count =0 ;//统计字段数 正确的话应该有 d-1
            int d = 0; //一共有多少段
            if(len%lenSub ==0){ 
                d = len/lenSub -1;
                for(int  j=i;j+lenSub<=len;j+=lenSub){ 
                    String sub2 = s.substring(j,j+lenSub);
                    if(sub.equals(sub2)){ 
                        count++;
                    }
            }
            if(count == d){ 
                return true;
            }
            }
        }
        return false;
    }
}

优化子串 flag

class Solution { 
    public boolean repeatedSubstringPattern(String s) { 
        for(int i = 1; i < s.length(); ++i){ 
            if(s.length()%i == 0){ 
                String t = s.substring(0, i);
                boolean flag = true;
                for(int j = i; j + i <= s.length(); j += i){ 
                    if(!t.equals(s.substring(j, j + i))){ 
                        flag = false;
                        break;
                    }
                }
                if(flag) return true;
            }
        }
        return false;
    }
}

优化逐个比较
在这里插入图片描述

class Solution { 
    public boolean repeatedSubstringPattern(String s) { 
        int n = s.length();
        for (int i = 1; i * 2 <= n; ++i) { 
            if (n % i == 0) { 
                boolean match = true;
                for (int j = i; j < n; ++j) { 
                    if (s.charAt(j) != s.charAt(j - i)) { 
                        match = false;
                        break;
                    }
                }
                if (match) { 
                    return true;
                }
            }
        }
        return false;
    }
}

2. 字符串匹配

在这里插入图片描述

class Solution { 
    public boolean repeatedSubstringPattern(String s) { 
        return (s + s).indexOf(s, 1) != s.length();
    }
}

【总结】

1. 扩展思路 KMP算法

2.思路二正确性证明

在这里插入图片描述

3.优化细节

3.1 子串长度至多等于原字符串除以2
3.2 flag标志+ break提前终止

转载链接：https://leetcode-cn.com/problems/repeated-substring-pattern/solution/zhong-fu-de-zi-zi-fu-chuan-by-leetcode-solution/
参考链接：https://leetcode-cn.com/problems/repeated-substring-pattern/solution/zhong-fu-de-zi-zi-fu-chuan-by-leetcode-solution/