Leetcode 459. 重复的子字符串【C++】

地址：https://leetcode-cn.com/problems/repeated-substring-pattern/

题目

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:

输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。

示例 2:

输入: "aba"
输出: False

示例 3:

输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

解题思路

看了题目之后我个人大概两个方向的思路，一是从最短的子串（一个字符的子串）开始判断，如果长度为 l 的子串不满足题目要求，则继续判断长度为 l + 1 的子串；另一个思路是先将原字符串等分为多个长度相等的子串，再判断各个子串是否相同。

综合来看，第二种思路过滤掉了长度不合适的子串，应该更理想一些，我也正是采用了这种思路解题。

首先要将长度为 len 的字符串划分为多个子串，可能的最少个数为 2 ，最多个数则一定是 len ，所以外层循环从 2 到 len 遍历并在循环体内判断是否可以等分字符串，如果可以则进一步判断等分的 i 个子串是否相同，一旦遇到各子串均相同的情况则返回 true ，否则遍历完所有可能的情况后返回 false 。

代码

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int len = s.length();
        //先判断是否可以分为i个长度相等的子串，再判断各子串是否相同
        for (int i = 2; i <= len; i++) {
            if (len % i == 0) {
                int l = len / i;  //子串长度
                string st = s.substr(0, l);  //将后续子串与第一个子串比较
                bool find = true;
                for (int j = 1; j < i; j++) {
                    if (st != s.substr(l * j, l)) {
                        find = false;
                        break;
                    }
                }
                if (find) return true;
            }
        }
        return false;
    }
};