Star

Leetcode 459. Repeated Substring Pattern

Posted on | In |

一道很简单的题。但是一直在调corner case，好不容易写完了再感受下速度和别人写的代码，差距太大了。心疼三秒钟。

Question:

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: 

1
2
3
4
5
Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.

Example 2: 

1
2
3
Input: "aba"
Output: False

Example 3: 

1
2
3
4
5
Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

Explanation:

原理很简单，就是每次得到一个substring，往后检查相同长度的下一段string。要注意的是，遍历的index只要到length/2就行了，毕竟至少也要重复两遍的。

Code:

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) {
        if(str == null || str.length() <= 1) return false;
        int len = str.length();
        for ( int i=0; i<=len/2; i++) {
            boolean flag = true;
            if (len%(i+1) != 0 || len == i+1) continue;
            String subString = str.substring(0,(i+1));
            int start = i+1;
            int end = start * 2;
            while (end<=len) {
                if (!subString.equals(str.substring(start,end))){
                    flag = false; break;
                }
                start = start + i+1;
                end = end + i+1;
            }
            // System.out.println(flag);
            if (flag) return true;
        }
        return false;
    }
}