看到这个第一个想法是推规律，利用规律去写，最简单的还是暴力写法。写完了之后再去想代码优化。

暴力解法

核心思路：

  • 将每个 （总长度 % 子串长度）为0的情况都循环检查
  • 检查的方式就是判断当前位置和前一个子串长度位置的字符是否相等

类似于"qweqweqwe",当检查到子串长度为3时，我们会判断下标3和0是否相等，4和1是否相等......

c++

class Solution {
public:
    bool repeatSubstring(string str) {
        // write code here
        int len = str.size();
        for(int i=1; 2*i <= len; i++){  //这里的i为子串长度，子串是不可能超过一半的
            if(len % i == 0){           //总长度 % 子串长度 必须为0
                bool flag = true;
                for(int j=i; j<len; j++){
                    if(str[j] != str[j-i]){  //和自己前面一个子串长度的地方进行比对
                        flag=false;
                        break;
                    }
                }
                if(flag) return true;  //这个循环能走完，说明 i 长度的子串可以通过重复，拼成初始字符串
            }
        }
        return false;  //字串长度超过一半，直接false即可
    }
};

优雅解法

核心思路：

  • 将字符串再重复叠加一下，两个str加在一起，去掉第一个字符，那么str一定是（str + str）的子串
  • 此时我们只需要判断找到的子串初始位置在哪里即可。
    • 如果已经到了str.size(),说明起始位置已经到了第二个子串，寻找失败。
    • 如果在str.size()之前就找到了，那么起始位置一定是第一个str中第二个子串开始的地方

c++

class Solution {
public:
    bool repeatSubstring(string str) {
        return (str + str).find(str, 1) != str.size()
    }
};

python

class Solution:
    def repeatSubstring(self , str: str) -> bool:
        return (str + str).find(str, 1) != len(str)

像这种使用字符串重复叠加的方法，而使得问题变的简单的情况，之前也做过一个有点点类似的题，是旋转字符串。