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

超、凢脫俗 2022-11-30 12:28 183阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 【解答思路】 ####

###### 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;
        }
    }

**优化 逐个比较**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

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. 字符串匹配 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]

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

#### 【总结】 ####

###### 1. 扩展思路 KMP算法 ######

###### 2.思路二正确性证明 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]

###### 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/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/d21d1deac70742a39175b595e3767ab3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/ec69d10c6cff4234adba59d34e5d5d2e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/7a98deab84a14099be8e49ab1501a891.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/f0c6da212fe1490ca09972a226ecf3db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/85fee85747ed4d6bbbbafdf576406361.png