leetcode解题: Repeated Substring Pattern (459)

发表于 | 分类于

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.

Example 1:
Input: “abab”

Output: True

Explanation: It’s the substring “ab” twice.
Example 2:
Input: “aba”

Output: False
Example 3:
Input: “abcabcabcabc”

Output: True

Explanation: It’s the substring “abc” four times. (And the substring “abcabc” twice.)

解法1：O(k * N), k是n的约数个数，n是字符串的长度

由于要分成相同的几个字串相连，那么字串的长度一定是原字符串的一个约数。这种情况下，约数的个数是有限制的，1 到 n / 2。
暴力解法，从n/2到1一个一个试，然后拼接出原字符长度比较。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool repeatedSubstringPattern(string str) {
        if (str.empty()) return false;
        int n = str.size();
        for (int i = n / 2; i >= 1; --i) {
            if (n % i == 0) {
                string sub = str.substr(0, i);
                string copy = "";
                for (int j = 0; j < (n / i); ++j) {
                    copy += sub;
                }
                if (str.compare(copy) == 0) {
                    return true;
                }
            }
        }
        return false;
    }
};

Java

1

解法2： KMP with O(N) Time

本题还有KMP的解法，显然不是我想出来的。先把网上看到的解释贴在这里。
用到的关于KMP的算法的详细说明。
深深的怀疑面试会期望给出这个答案。。
还有是关于本题的解释