leetcode【字符串—简单】459.重复的子字符串

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为链表专题。

题目

题目来源leetcode

leetcode地址：459. 重复的子字符串，难度：简单。

题目描述(摘自leetcode)：

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。示例 2:
输入: "aba"
输出: False示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

本地调试代码：

class Solution {public boolean repeatedSubstringPattern(String s) {...}public static void main(String[] args) {System.out.println(new Solution().repeatedSubstringPattern("aba"));}}

题解

正文

NO1：整除比较法(初始思路)

思路： 先自己想思路，有了思路直接code就行，当前提交没有看题解。

核心点：一个子串重复多次构成、只含有小写英文字母、长度不超过10000
思路：
1、确定每次重复的个数，这是我们能够确定的。例如"abababab"，长度为8。那么每次重复个数情况有1、2、4。(for循环模一下即可判定)
2、直到重复个数之后就好办了，重新开个for循环从指定位置开始指定长度比较就ok，一旦一组比较下来都相同直接返回true，否则进行其他重复个数情况二次比较！

代码：

public boolean repeatedSubstringPattern(String s) {String subStr = "";for (int i = 1; i < s.length(); i++) {//每i个数能够成对出现if(s.length() % i == 0){subStr = s.substring(0,i);int j = i;for (; j < s.length(); j+=i) {if(!Objects.equals(subStr,s.substring(j,j+i))){break;}}if(j == s.length()){return true;}}}return false;
}

同样与这个思路一致，将直接取两个子串方式改为取两个指针来从左到右进行比较，看下是否有时间上的优化：

• 注释的内容表示被替换了

public boolean repeatedSubstringPattern(String s) {//        String subStr = "";for (int i = 1; i < s.length(); i++) {if(s.length() % i == 0){//                subStr = s.substring(0,i);int j = i;for (; j < s.length(); j+=i) {//左右指针比较//                    if(!Objects.equals(subStr,s.substring(j,j+i))){//                        break;//                    }/*******直接取子串=>左右连续对比*******/int subStrCur = 0;int jCur = j;while(subStrCur != i){if(s.charAt(subStrCur) != s.charAt(jCur)){break;}subStrCur++;jCur++;}if(subStrCur != i){break;}/**************/}if(j == s.length()){return true;}}}return false;
}

效果感觉不咋地，反而比我们使用subString()取字符串来的效率高，现在去看下其他人题解。

NO2：KMP解决（核心，重点掌握）

思路：利用KMP算法求得next数组，接着通过next数组最后一个元素的指向的最长重复前缀位置来进行判断是否当前字符串是否为重复的子字符串。

举例：
例1：s="abababab"  next[] = [-1, -1, 0, 1, 2, 3, 4, 5]next数组最后一个位置为5，指向原字符串中的倒数第三个，使用原字符串长度减去该位置-1，8-5-1=2，2就指的是对应子串的长度，接着使用字符串长度进行%,若是=0，表示其为重复子串。公式为：s.length() % (s.length() - targetPos - 1) == 0例2：s="ababcddc" next=[-1, -1, 0, 1, -1, -1, -1, -1]最后位置为-1，直接判定没有重复字符串。例3：s="ababcdab" next[] = [-1, -1, 0, 1, -1, -1, 0, 1]最后位置为1，同理代入，8%(8-1-1)=2，没有整%，所以直接判断没有

代码：时间复杂度O(n)

public int getNext(String s) {//KMP求得next数组        int next[] = new int[s.length()];int j = -1;next[0] = -1;for (int i = 1; i < s.length(); i++) {while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {j = next[j];}if (s.charAt(i) == s.charAt(j + 1)) {j++;}next[i] = j;}return next[s.length() - 1];
}public boolean repeatedSubstringPattern(String s) {//使用KMP取到最后一个元素重复元素前缀位置int targetPos = getNext(s);if (targetPos == -1) {return false;}if (s.length() % (s.length() - targetPos - 1) == 0) {return true;}return false;
}

NO3：超级整除法（参考大佬）

使用KMP最后的执行耗时才击败了62%的人，接着就去看了看大佬的代码，真的是特别特别巧妙！

思路：相对于NO1的整除法，中间有很多没必要二次比较的情况，并且我是从小数重复串进行一一比对的，这里使用大数重复串比较，并且省去了一些没必要重复比较的情况。

假设某个字符串长度为8，按照正常思路顺序，先取最长重复串长度为4个4个比较、失败取2个2个、失败再取1个1个。
其实后面的两次就是没有必要的，我们举个例子："abababac"①abab abac  (失败)②ab ab ab ac (失败)③a b a b a b b a c (失败)
仔细看第二步，假设它是重复串组成ab ab ab ab，那么就必然就有abab abab判断成功，那么①失败，下面的②③比较自然没有必要了。其规律就可以找到凡是某个最大子串匹配失败，那么其整除的情况(也就是②③)直接可以省略掉。上面说明了没必要重复比较的情况，下面再举一个长度为6的例子："ababab"①aba bab (失败)②ab ab ab （成功）
对于该种情况，第②步是不用被省略的，因为第一组最大重复数量为3，其并不能整除2，那么对重复长度为2的自然会进行一一比较，这里就有一个问题，我们该如何进行比较？上面长度为6的有三组，难道要一个一个进行比？从大佬的代码中我又看到了解答，所有任意情况只要比较1次即可，对于②中取出abab abab这两个，刚开始我也贼蒙蔽，不过之后就感叹其妙的地方了。
重复长度2，第一组[0,6-2-1]=>[0,3] 第二组[2,6-1]=>[2-5],假设三组子字符串都先相同，那么任意两组之和也必然相同，借助这个要点，我们即可将多组比较化为2组比出结果。

代码：

public boolean repeatedSubstringPattern2(String s) {int len = s.length();int parts = 2;//从2开始，之后取子串len/2、len/3，保证子串从最大长度开始进行比较重复int noRepeatLen = len;while (noRepeatLen > 1) {if (noRepeatLen % parts == 0) {int k = len / parts;//子串长度//取出两组进行比较if (Objects.equals(s.substring(0, len - k), s.substring(k))) {return true;}//去除重复的整除情况，在除数上进行操作noRepeatLen /= parts;while (noRepeatLen % parts == 0) {noRepeatLen /= parts;}}parts++;}return false;
}

NO4、超简洁解法（看看就好）

好家伙，两行解决？还是很妙的。举两个例子就可以看懂了。

思路：

① s="abac" 不重复情况  "ababca"s+s = "abacabac"，去头去尾"bacaba"
② s="abab"s+s = "abababab"，去头去尾"bababa" √
③ s="aaaa"s+s = "aaaaaaaa"，去头去尾"aaaaaa" √这种方式很巧妙，通过拼接方式去头去尾看其中是否存在原字符串。若是有重复的必然拼接中有对应重复的！

代码：

public boolean repeatedSubstringPattern(String s) {String str = s + s;return str.substring(1, str.length() - 1).contains(s);
}

参考文章

[1]. leetcode题解

[2]. 代码随想录—459.重复的子字符串

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！
欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料
Q群：851968786 我们可以一起探讨学习
注明：转载可，需要附带上文章链接