Repeated Substring Pattern

Problem

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.)

Solution

Smart O(1) Solution:

public class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String str = s + s;
        return str.substring(1, str.length() - 1).contains(s);
    }
}

Regular O(1.5) Solution:

public class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int len = s.length();
        outerLoop:
        for (int i = len / 2; i >= 1; i--) {
            if (len % i == 0) { 
                String pattern = s.substring(0, i);
                for (int j = 1; j < len / i; j++) {
                    if (!s.substring(j * i, j * i + i).equals(pattern)) continue outerLoop;
                }
                return true;
            }
        }
        return false;
    }
}

Analysis

The first problem is very interesting and smart
We concatenate two given string and then drop the first and the last character
We return true if we can find original string from it

The second solution uses regular way to check if given string has repeated pattern
We starts from the half of string because a valid string must have at least two repeated pattern
We use len % i == 0 to get the divisor of length
Then we use another loop to check if each substring follows the pattern
As long as we find out one pattern which is followed by all substring, we return true