459. Repeated Substring Pattern

https://leetcode.com/problems/repeated-substring-pattern/

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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.)

java

https://discuss.leetcode.com/topic/67992/java-simple-solution-with-explanation

  1. The length of the repeating substring must be a divisor of the length of the input string
  2. Search for all possible divisor of str.length, starting for length/2
  3. If i is a divisor of length, repeat the substring from 0 to i the number of times i is contained in s.length
  4. If the repeated substring is equals to the input str return true
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public class Solution {
    public boolean repeatedSubstringPattern(String str) {
    int l = str.length();
    for(int i=l/2; i>0; i--){
    if(l%i == 0){
    int m = l/i;
    String subS = str.substring(0, i);
    StringBuilder sb = new StringBuilder();
    for(int j=0; j<m; j++)
    sb.append(subS);
    if(sb.toString().equals(str)) return true;
    }
    }
    return false;
    }
    }

https://discuss.leetcode.com/topic/67992/java-simple-solution-with-explanation/2

Added a small check in your code and time reduced from 48 ms to 18 ms. Just return if any of the substring will not match. No need to create the whole string.

23ms, 76.61%, Dec 30th, 2016

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public boolean repeatedSubstringPattern(String str) {
int l = str.length();
for(int i=l/2; i>0; i--){
if(l%i == 0){
int m = l/i;
String subS = str.substring(0, i);
int j;
for(j=1; j<m; j++){
if(!subS.equals(str.substring(j*i, i+j*i))) break;
}
if(j==m)
return true;
}
}
return false;
}
}

https://discuss.leetcode.com/topic/67611/share-my-simple-solution

Try every possible substring, then check.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
public boolean repeatedSubstringPattern(String str) {
int len = str.length();
if(len<2) return false;
for(int i=2;i<=len;i++){
if(len%i!=0) continue;
if(check(str, i)) return true;
}
return false;
}
public boolean check(String str, int repeat){
int len = str.length();
String cand = str.substring(0, len/repeat);
for(int i=0;i<len;i++){
if(str.charAt(i)!=cand.charAt(i%(len/repeat))) return false;
}
return true;
}
}

https://discuss.leetcode.com/topic/68210/from-intuitive-but-slow-to-really-fast-but-a-little-hard-to-comprehend

Solution 1:
Let us start with the very naive solution. It uses 188 ms to solve 100 test cases. The idea is that when we see a character in str that matches the very first character of str, we can start to hoping that str is a built by copies of the substring composed by all characters before the reappearance of the its first character.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
public boolean repeatedSubstringPattern(String str) {
int l = str.length();
if(l == 1) {
return false;
}
StringBuilder sb = new StringBuilder();
char first = str.charAt(0);
sb.append(first);
int i = 1;
while(i <= l / 2) {
char c = str.charAt(i++);
if(c == first && isCopies(str, sb.toString())) {
return true;
}else {
sb.append(c);
}
}
return false;
}
private boolean isCopies(String str, String substr) {
if(str.length() % substr.length() != 0) {
return false;
}
for(int i = substr.length(); i < str.length(); i += substr.length()){
if(!str.substring(i).startsWith(substr)){
return false;
}
}
return true;
}
}

Solution 2:
The problem of the first solution is that we do not use the knowledge of failed matching, and the Knuth-Morris-Pratt algorithm is a classic example of how knowledge of failed tries can be use to guide future search.

In fact we only need to compute the pattern table (the lps array, see below) in the Knuth-Morris-Pratt algorithm.

The entry lps[i] is the length of the longest proper prefix that is also a suffix of (s[0], …, s[i]), or equivalently, length of the longest prefix that is also a proper suffix of (s[0], …, s[i]). lps[0] is 0, since a single - character string has no proper prefix or proper suffix. Here is a very detailed explanation on the KMP algorithm and how lps is computed dynamically.

After we get lps, we relate the property of the lps table to the property of a string being constructed by joining copies of its substring.

One on hand, if str = (s[0], …, s[km - 1]) is constructed by joining m copies of its substring substr = (s[0], …, s[k-1]), and assuming that substr is the finest making blockstr can be boiled down to, meaning str is not constructed by joining copies of any proper substring of substr. Then we must have lps[km - 1] equals (m - 1)k.

On the other hand, assuming that the longest proper prefix of string str that is also a suffix, and the remaining string remainderStr obtained by removing prefix from str satisfies the following 3 properties:

remainderStr is a proper substring of str,
|str| is divisiable by |remainderStr|,
remainderStr is a prefix of prefixStr.
We can show by induction that str is constructed by joining copies of remainderStr.
Here is the code. It solve the 100 test cases in 29ms. A great improvement over the native approach! Remember the statement above, since we are going to use it again.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public boolean repeatedSubstringPattern(String str) {
int l = str.length();
int[] lps = new int[l];
int leading = 1;
int chasing = 0;
while(leading < l) {
if(str.charAt(chasing) == str.charAt(leading)) {
chasing++;
lps[leading] = chasing;
leading++;
}else {
if(chasing > 0) {
chasing = lps[chasing - 1];
}else {
chasing = 0;
leading++;
}
}
}
int lp = lps[l - 1];
return (lp > 0 && l % (l - lp) == 0 && str.startsWith(str.substring(lp)));
}
}

Solution 3:

Can the problem be solved efficiently without KMP? The following solution runs even faster (23ms on 100 test cases)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
public boolean repeatedSubstringPattern(String str) {
int l = str.length();
for(int i = l / 2; i > 0; i--) {
if(l % i == 0) {
String substr = str.substring(0, i);
int j = i;
while(j < l) {
if(!str.substring(j, j + i).equals(substr)){
break;
}else {
j += i;
}
}
if(j == l) {
return true;
}
}
}
return false;
}
}

Solution 4:

Want clearer code that runs even faster ? Here is it. The idea is stated at the end of the explanation for solution 2. Without really find the longest proper prefix that is also a suffix as in solution 2 and see whether the three properties are matched, we just test each remainderStr, from the longest possible that satisfies condition 1 and 2, that whether the corresponding prefix and suffix match each other. It solve 100 test cases in 16ms. So maybe now, you really want to prove the statement since it lead to such a clean and fast solution? It is not hard to prove by induction.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public boolean repeatedSubstringPattern(String str) {
int l = str.length();
for(int i = (l + 1) / 2; i < l; i++) {
if(l % (l - i) == 0) {
String prefix = str.substring(0, i);
String remainder = str.substring(i);
String suffix = str.substring(l - i);
if(str.startsWith(remainder) && suffix.equals(prefix)){
return true;
}
}
}
return false;

cpp

https://discuss.leetcode.com/topic/67652/c-o-n-using-kmp-32ms-8-lines-of-code-with-brief-explanation

First, we build the KMP table.

Roughly speaking, dp[i+1] stores the maximum number of characters that the string is repeating itself up to position i.
Therefore, if a string repeats a length 5 substring 4 times, then the last entry would be of value 15.
To check if the string is repeating itself, we just need the last entry to be non-zero and str.size() to divide (str.size()-last entry).

1
2
3
4
5
6
7
8
9
10
bool repeatedSubstringPattern(string str) {
int i = 1, j = 0, n = str.size();
vector<int> dp(n+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[n]&&dp[n]%(n-dp[n])==0;
}

https://discuss.leetcode.com/topic/67652/c-o-n-using-kmp-32ms-8-lines-of-code-with-brief-explanation/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Same implementation.

My p[i] stands for longest common string length of prefix string and the string ended with position i.

The important point is the last one: len % (len - p[len - 1]) == 0

for a string like below, if p[len-1] = 15, len=20:

#####~~~~~^^^^^$$$$$
#####~~~~~^^^^^$$$$$

by p[len-1] = 15, we know the strings colored red are the same.

so you can infer that:

##### == ~~~~~

~~~~~ == ^^^^^

^^^^^ == $$$$$

The whole is repeating as #####

the length of it is 5, which can be completely divided by len.

That's how this final condition works.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool repeatedSubstringPattern(string str) {
int len = str.length(), i = 0, j = 1;
int p[len];
while (j < len)
if (str[i] == str[j])
p[j++] = ++i;
else {
if (!i)
p[j++] = 0;
else
i = p[i - 1];
}
return p[len - 1] && len % (len - p[len - 1]) == 0;
}

python

https://discuss.leetcode.com/topic/68206/easy-python-solution-with-explaination

Basic idea:

  1. First char of input string is first char of repeated substring
  2. Last char of input string is last char of repeated substring
  3. Let S1 = S + S (where S in input string)
  4. Remove 1 and last char of S1. Let this be S2
  5. If S exists in S2 then return true else false
  6. Let i be index in S2 where S starts then repeated substring length i + 1 and repeated substring S[0: i+1]
1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def repeatedSubstringPattern(self, str):
"""
:type str: str
:rtype: bool
"""
if not str:
return False

ss = (str+str)[1:-1]
return ss.find(str) != -1
谢谢你,可爱的朋友。