【問題描述】[中等]

【解答思路】

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-1int 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/

總結

以上是生活随笔為你收集整理的[Leetcode][第459题][JAVA][重复的字符串][子串][匹配]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。