Easy python solution with explaination


  • 129
    R

    Basic idea:

    1. First char of input string is first char of repeated substring
    2. Last char of input string is last char of repeated substring
    3. Let S1 = S + S (where S in input string)
    4. Remove 1 and last char of S1. Let this be S2
    5. If S exists in S2 then return true else false
    6. Let i be index in S2 where S starts then repeated substring length i + 1 and repeated substring S[0: i+1]
    def repeatedSubstringPattern(self, str):
    
            """
            :type str: str
            :rtype: bool
            """
            if not str:
                return False
                
            ss = (str + str)[1:-1]
            return ss.find(str) != -1
    

  • 0
    K

    thank you for your amzaing solution!!!!


  • 2
    E

    @rsrs3 Thanks for your amazing solution! Could you share your thoughts on how to technically prove this solution is correct? It passed all the test cases, but I still have no idea why it works.


  • 0
    R

    Good solution @rsrs3 but as @Eastknight said it would be nice if we know why this works.


  • 40
    Q

    @rohan5 @Eastknight

    Let's say T = S + S.
    "S is Repeated => From T[1:-1] we can find S" is obvious.

    If from T[1:-1] we found S at index p-1, which is index p in T and S.
    let s1 = S[:p], S can be represented as s1s2...sn, where si stands for substring rather than character.
    then we know T[p:len(S) + p] = s2s3...sn-1sns1 = S = s1s2...sn-2sn-1sn.
    So s1 = s2, s2 = s3, ..., sn-1 = sn, sn = s1,Which means S is Repeated.

    edit:
    I should fix this because len(si) == len(sj) has not be proved. The procedure becomes complicated :-(
    Let s1 = S[:p], S can be represented as s1X1.
    then S = X1s1 = s1X1 (A).

    1. len(X1) < len(s1) is false because if so we should find S in T[1:-1] at index len(X1) rather than len(s1) = p.

    2. len(X1) == len(s1) and (A) => X1 = s1 => S is Repeated.

    3. len(X1) > len(s1) and (A) => X1 has prefix s1 so can be represented as s1X2.
      X1 = s1X2 and (A) => s1X2s1= s1s1X2 =>X2s1 = s1X2 (B).
      len(X2) < len(s1) is false because if so (A) and (B) => S = X2s1s1 = s1s1X2 and we should find S at index len(X2) rather than p.

      As long as len(Xi-1) > len(s1), we can get Xis1 = s1Xi through the prefix step and prove len(Xi) < len(s1) is false through the index step. Eventually we can get a Xn, len(Xn) == len(s1) and Xns1 = s1Xn => Xn = s1 => S = s1X1 = s1s1X2 = ... = s1s1...s1Xn-1 = s1s1...s1s1Xn => S is Repeated.


  • 45

    Wow that's nice. But the code can be nicer, at least better use the in operator:

    def repeatedSubstringPattern(self, str):
        return str in (2 * str)[1:-1]

  • 2
    R

    @QuentinLewes thanks! this makes it clear!


  • 0
    F
    This post is deleted!

  • -1
    M

    Awesome!!!! Best solution for this problem!!


  • 4
    H

    @QuentinLewes
    Perhaps a simpler proof for From T[1:-1] we can find S => S is Repeated:
    Suppose S = s1s2, where s1 in S[1:] and s2 in S[:-1], which means S = s1s2 = s2s1 and WLOG we can assume len(s1) < len(s2).
    We only need to prove that s2 = s1...s1. This is directly from s1s2 = s2s1 as well (if you compare char by char).


  • 1
    L
    This post is deleted!

  • 26
    D

    The explanation for why that works is pretty straight forward.

    Consider a string S="helloworld". Now, given another string T="lloworldhe", can we figure out if T is a rotated version of S? Yes, we can! We check if S is a substring of T+T.

    Fine. How do we apply that to this problem? We consider every rotation of string S such that it's rotated by k units [k < len(S)] to the left. Specifically, we're looking at strings "elloworldh", "lloworldhe", "loworldhel", etc...

    If we have a string that is periodic (i.e. is made up of strings that are the same and repeat R times), then we can check if the string is equal to some rotation of itself, and if it is, then we know that the string is periodic. Checking if S is a sub-string of (S+S)[1:-1] basically checks if the string is present in a rotation of itself for all values of R such that 0 < R < len(S).


  • 17
    P

    Wow. It is super smart. The best solution for the problem.
    Let me make a note for future reference.

    If the string S has repeated block, it could be described in terms of pattern.
    S = SpSp (For example, S has two repeatable block at most)
    If we repeat the string, then SS=SpSpSpSp.
    Destroying first and the last pattern by removing each character, we generate a new S2=SxSpSpSy.

    If the string has repeatable pattern inside, S2 should have valid S in its string.


  • -1
    L

    @QuentinLewes thanks, the explanation is clear and easy to follow.


  • 0
    L
    This post is deleted!

  • -1
    S

    perfect solution ! thanks for contribution!


  • -1
    A

    Simple and very good solution.

    Not only for python, ur code helps everyone .. thanku


  • -1
    A

    Here is a java solution of the same idea:

    public boolean repeatedSubstringPattern(String s) {
            String c = (s + s).substring(1, s.length() + s.length() - 1);
            return c.indexOf(s) != -1;
    }
    

  • 0
    C
    This post is deleted!

  • 0
    C
    This post is deleted!

Log in to reply
 

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