RepeatedSubstringPattern [source code]

public class RepeatedSubstringPattern {
static
/******************************************************************************/
public class Solution {
    public boolean repeatedSubstringPattern(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        if (n == 0) return false;
        int i = 1;
        for (; i <= n / 2; i++) {
            if (n % i != 0) continue;
            int m = n / i;
            int j = 0;
            for (; j < i; j++) {
                int k = 1;
                for (; k < m; k++) {
                    if (chars[j] != chars[j + k * i]) break;
                }
                if (k < m) break;
            }
            if (j == i) break;
        }
        return !(i > n / 2);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        RepeatedSubstringPattern.Solution tester = new RepeatedSubstringPattern.Solution();
        String[] inputs = {"a", "abab", "aba", "abcabc", "abcabcabcabc"};
        for (String s : inputs) System.out.printf("%s -> %s%n", s, tester.repeatedSubstringPattern(s));
    }
}

穷搜也未必就是一件很简单的事情, 类似前面 UglyNumber 的时候, 那个穷搜 factor 的算法;

这题刚开始也是没有思路的, 因为我对于穷搜的算法还是不熟悉, 后来想到了用这个算法来进行一个穷搜;

这里还是有几个技术难点的:

  • 这里的 i 和 m, 其实都属于是 length 型的概念,这个前面已经总结过一次了, 这种概念出现在 loop 的 header 里面的时候, 是要取小于号的;
  • 这个题目还有一个技术上不好处理的地方, 在于怎样完成一个breaking out of multiple loops的问题; 这个以前网上搜过, 一般常见的方法包括把里面的 loop 单独放到一个函数里面去, 或者用 label; 这里我的方法不是这些, 而是一个在大多数的其他的语言里也通用的做法, 就是一个对 termination condition 的判断, 尤其是对 loopvar 的取值的判断;

注意这个方法的两个要点:

  1. loopvar 的 declaration 一定要放在 loop 的 body 外面;
  2. forloop 的时候可能有点不明显; 不过实际上最后的那个类似i++的东西, 一般都是在body 执行玩了之后才执行的, 所以我们才可以在循环的外面结束以后来判断是否是 break 出来的, 因为 break 出来的, 是在 body 内部 break 的, i++一般还没有来得及执行, 对于一个i < n这样的 loop, 最后 i 就没有机会到达 n 而完成自然的 termination;

最后的速度是29ms (78%), 还算可以, 看来这个问题大部分人还是得用穷搜来做;

这个算法的复杂度还可以再降, 因为我们 i 找的其实是 n 的 factor, factor 如果你从1开始搜, 是不用一直搜到n - 1的:
The number of factors is always bounded by O(sqrt(n)). Factors come in pairs, i.e., n = a b. The smaller one of a and b must be no larger than sqrt(n); otherwise, we have a > sqrt(n) and b > sqrt(n) and thus a b > n. Therefore, there are at most 2sqrt(n) = O(sqrt(n)) factors, and the worst case runtime for this algorithm is O(n^1.5).(最后这个1.5是针对他那个帖子的那个算法说的, 未必适用于我这个算法. 想了一下, 好像也适用于我这个算法, 每个 iteration 最多是O(n).);

这个是他们讨论的算法: 

public boolean repeatedSubstringPattern(String str) {  
        int len = str.length();  
        for(int i=len/2 ; i>=1 ; i--) {  
            if(len%i == 0) {  
                int m = len/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;  
}

总体思路是差不多的, 只不过他们比较的是 substring, 我是用 character 来一个一个的比较的, 所以看起来比他们多一个循环;

不对, 这个人的意思好像不是 i的边界只要到sqrt(n)就行了(这个是不对的);这个人只是单纯的针对复杂度进行计算而已; 但是我这个复杂度还是可以优化, 最起码跑到Math.sqrt(n)就足够了;
最后果然是可以改的, 就是 boundary case 的时候要稍微小心一点, 包括最后的几个对于 Loop Var 的判断都要稍微更改; 速度最后优化到了25(83);

后来想了一下, 这个人的说法是不对的, 比如n=6的情况下, 我们i=3就要尝试, 这个就是大于sqrt(6)的.
所以边界还是应该设置在n/2而不是sqrt(n);

后面想了一下, 他这里关于 sqrt 的讨论是对的. 他这里说的是总共会有2sqrt(n)个 iteration, 而不是说用这个来作为边界; 所以我们实际上的 iteration 的 header 跑了O(n) 个, 但是实际上只有2sqrt(n) 个 iteration 里面不是 trivial 的: 这些 iteration 里面可能产生 worst case of O(n)的时间, 所以最后的时间应该是O(n) + O(n ^ 1.5) = O(n ^ 1.5);

如果非要用 sqrt(n)作为边界, 那么可以用这个代码: 

int range=(int)Math.sqrt(len);  
for(int i=2;i<=range;i++){  
    if(len%i!=0) continue;  
    if(check(str, i)) return true;  
    if(check(str, len/i)) return true;  
}  
if(check(str, len)) return true;  
return false;

Corner Case 什么的就没管了. 你计算一下, 这个速度其实是要低一些的, 是sqrt(n) (2 n);

discussion里面还给了其他好玩的代码: 

class Solution {  
public:  
    bool repeatedSubstringPattern(string str) {  
        string nextStr = str;  
        int len = str.length();  
        if(len < 1) return false;  
        for(int i = 1; i <= len / 2; i++){  
            if(len % i == 0){  
                nextStr = leftShift(str, i);  
                if(nextStr == str) return true;  
            }  
        }  
        return false;  
    }  

    string leftShift(string &str, int l){  
        string ret = str.substr(l);  
        ret += str.substr(0, l);  
        return ret;  
    }  
};

这个代码就避免了自己一个一个的去比较. 这个代码可以简化: 

public boolean repeatedSubstringPattern(String str) {  
    int n = str.length();  
    for (int i = 1; i <= n / 2; i++)  
        if (n % i == 0 && str.startsWith(str.substring(i)))  
            return true;  
    return false;  
}

现在在尝试理解他们用的一个基于 KMP 的算法, 简直是噩梦;
不过在一个帖子里面有一个人认为我这个类似穷搜的算法其实是比 KMP 快的;

Problem Description

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.)
Difficulty:Easy
Category:Algorithms
Acceptance:38.17%
Contributor: YuhanXu
Companies
amazon google
Related Topics
string
Similar Questions
Implement strStr()

results matching ""

    No results matching ""