repeated-substring-pattern

Repeated Substring Pattern – LeetCode 459

Problem

Description

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Answer

Original

Code

class Solution {
public:
    bool repeatedSubstringPattern(string str) {
        for (int i = str.size() / 2; i >= 1; --i) {
            if (str.size() % i == 0) {
                string t;
                for (int j = 0; j != str.size() / i; ++j)
                    t += str.substr(0, i); 
                if (t == str) return true;
            }
        }
        return false;
    }
};

思路

依次从头构筑可能出现的重复串，而后进行依次比对。时间复杂度$O(n^{2})$，空间复杂度$O(1)$。
耗时$54$ ms，排名$78.48\%$

Better

思路

使用dp来记录当前项的重复对应项，类似与KMP。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$29$ ms，排名$19.92\%$

Code

class Solution {
public:
    bool repeatedSubstringPattern(string str) {
        int i = 1, j = 0;
        vector<int> dp(str.size() + 1,0);
        while(i < str.size()){
            if(str[i] == str[j]) dp[++i] = ++j;
            else if(j == 0) ++i;
            else j = dp[j];
        }
        return dp[str.size()] && dp[str.size()] % (str.size() - dp[str.size()]) == 0;
    }
};