绍兴网站建设seo,网络销售是做什么,国内最新十大新闻,唐山海港经济开发区人才网【问题描述】[中等] 【解答思路】
1. 枚举
找出能整除的子串长度#xff0c;再用substring遍历匹配即可 时间复杂度#xff1a;O(N^2) 空间复杂度#xff1a;O(1)
class Solution {public boolean repeatedSubstringPattern(String s) {int len s.length();for(int i 1…【问题描述】[中等] 【解答思路】
1. 枚举
找出能整除的子串长度再用substring遍历匹配即可 时间复杂度O(N^2) 空间复杂度O(1)
class Solution {public boolean repeatedSubstringPattern(String s) {int len s.length();for(int i 1 ;ilen/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 ji;jlenSublen;jlenSub){String sub2 s.substring(j,jlenSub);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/
