Share my simple solution


  • 9

    Try every possible substring, then check.

    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;
        }
    }
    

  • 0

    perfect!perfect code.


  • 3
    T

    @YuTingLiu

    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;
    

    Maybe a little bit faster.


  • 1

    @troy351
    i think u r probably wrong, the substring's length could be varied from str.length() / 2 to 1, so there is nothing to do with the sqrt(len)


  • 1
    T

    @Lara
    Let's take str.length()==16 for example.
    original solution:

    i=2, check 2
    i=3, continue
    i=4, check 4
    i=5, continue
    i=6, continue
    i=7, continue
    i=8, check 8
    i=9, continue
    i=10, continue
    i=11, continue
    i=12, continue
    i=13, continue
    i=14, continue
    i=15, continue
    i=16, check 16
    

    my solution:

    i=2, check 2 && check 8
    i=3, continue
    i=4, check 4 && check 4
    check 16
    

    Of course, sqrt(len) matters a lot especially when str.length() is quite big, like 1 million.


  • 0

    @troy351 lol
    i didn't see u check the original len at the end
    thx for explaination


  • 0

    @YuTingLiu The lower bound of loop for(int i=0;i<len;i++) in method check seems can have a head start from len/repeat instead of 0 since string cand itself is a prefix of str with length len/repeat. Or you could check directly if(str.substring(len/repeat)) == str.substring(0, len-len/repeat).


  • 0

    @troy351 said in Share my simple solution:

    Of course, sqrt(len) matters a lot especially when str.length() is quite big, like 1 million.

    Yes, indeed using sqrt(len) as the loop upper bound can reduce time complexity from O(len) + o(len1+e) to O(len0.5) + o(len1+e) for any small e > 0.


  • 1
    A

    Simpler
    public class Solution {
    public boolean repeatedSubstringPattern(String str) {
    if(str == null || str.length() == 0)
    return false;
    int pos = (str+str).indexOf(str, 1);
    return pos != -1 && pos < str.length();
    }
    }


  • 0
    T

    @allen33 brilliant solution


  • 0
    N

    What is the complexity of this solution?


  • 0

    @nehad said in Share my simple solution:

    What is the complexity of this solution?

    I posted a time complexity analysis in my following post:
    6-line C++ solution no KMP with detailed time complexity analysis O(n^(1+1/loglog(n))) or o(n^(1+e))

    It needs to use the research of the estimated growth rate of number of divisors d(n) if you want a tight complexity estimate.


  • 0
    P

    It's so cool


  • 0

    @troy351 Just sharing my opinion.
    Your solution is correct, but I don't it's faster in the worst case than the one posted by @YuTingLiu . I think your implementation is slower by N(sqrt(N) - 1) character comparisons.

    First, I establish this assumption: each check take time N: for each check(str, i), we check for each j = 0..i - 1 that str.charAt(j) repeats len / i - 1 times afterwards, which takes len / i - 1 character-to-character comparison. Denote len by N, we know that each iteration we have to do i * (len / i - 1) comparisons. Let's say it's N comparisons each iteration.

    Since you are using the sqrt(N) here, I take it that we both consent that there are at most 2 * sqrt(N) divisors for N here.

    In your solution, you have sqrt(N) iterations, and you do two checks in each iteration. The comparisons done in your implementation is gonna be sqrt(N) * 2 * N.

    In @YuTingLiu 's solution:
    There are at most N iterations. But there are at most 2sqrt(N) divisors, so there are at most 2sqrt(N) iterations where i passes the mod test so as to activate the call to check. That means only 2sqrt(N) calls to check are made. So the total runtime of her solution is gonna be N + 2 * sqrt(N) * N.

    You can see that your algorithm actually costs N * (sqrt(N) - 1) more time than her solution.

    Her solution can actually benefit from a simple optimization: iterate i only through 2..N/2, in this way, her running time would be N/2 + 2 * sqrt(N) * N, this is even less.

    I tried both codes on the OJ, unfortunately the result is not quite corroborating the analysis: both your version and her version fluctuates between 69ms ~ 88ms across multiple submissions.

    There are caveats about this analysis: the analysis above only applies to worst case situations. Since the assumption that each check takes N comparisons(it does not terminate prematurely due to mismatch), and the claim that there are at most 2sqrt(N) divisors for N are both worst case assumptions.

    The speed contest might turn out differently in practical cases. If for a particular N, there are actually M divisors for it, then:

    • Your solution's # of character comparison: sqrt(N) + M * 2 * N
    • Her solutions's # of character comparison: N + M * N

    It is not so likely to prove deterministically the superiority of either solution in this case. Thus you are right that in saying that your solution may be faster.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.