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.

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

Tips:

从长度为1的substring开始试起试到长度为l/2，如果这个长度可以被整除，则重建一个重复substring的新string，如果新的string和老的string一样则返回true。如果循环结束返回false。

Complexity: O(n^2)??

Code：

public class Solution {
    public boolean repeatedSubstringPattern(String s) {
        if (s == null || s.length() == 0) return true;
        int l = s.length();
        for (int i = 1; i <= l / 2; i++) {
            if (l % i == 0) {
                int count = l / i;
                String sub = s.substring(0, i);
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < count; j++) {
                    sb.append(sub);
                }
                if (sb.toString().equals(s)) return true;
            }
        }
        return false;
    }
}