Very simple AC JAVA solution


  • 1
    K
    public class Solution {
        public boolean repeatedSubstringPattern(String str) {
           if(str==null || str.length()==0) return false;
          
           int l=str.length();
           
           for(int i=1;i<=l/2;i++){  //i=1 not 0
               if(l%i==0){
                   String prefix= str.substring(0,i);  
                   String suffix= str.substring(i);
                   if(suffix.length()%prefix.length()==0 && str.startsWith(suffix)) return true;   
               }
           }       
           return false;
        }
    }
    
    

    [added below to explain my thought on it]

    1.Let's say a valid string is 'abcabcabc'. Its pattern is 'abc', and then pattern repeats.

    1. I need to find this pattern ('abc'), and then check if the whole string follows the same pattern. I don't want to do a brute force check on this. What are my options?

    2. I use prefix in the code to find the 1st applicable pattern, then I make sure the suffix is also following the same pattern as the whole original string. I use 'str.startsWith(suffix)==true' to complete this check in my code.

    3. Why 'str.startsWith(suffix)==true' is enough? I could proof it by contradiction.

      Statement to prove: " If a given str is repetitive, then str.startsWith(suffix)==true"
      Proof by Contradiction: Let's say 'the str is repetitive', and 'str.startsWith(suffix)==false' is valid.
      But if 'str.startsWith(suffix)==false' (e.g. abacab), then 'str is not repetitive'
      So " If a given str is repetitive, then str.startsWith(suffix)==true"


  • 0
    R

    Its very precise and neat. What is the logic behind it ?


  • 0

    @kingseagle It seems that a copy of String prefix= str.substring(0,i) is unnecessary and only its length is needed. The loop upper bound i<=l/2 could be tightened to i<=sqrt(l) if you also check l/i in your loop because divisors of an integer always appear in pairs.


  • 0

    @rahul8590 said in Very simple solution:

    Its very precise and neat. What is the logic behind it ?

    The repetitive substring condition of string s is equivalent to if you could find its prefix p which is also a suffix as that the length difference is a divisor of s.length itself. The difference string will be the repetitive substring because the "shift" from prefix to suffix guarantees the duplicates of substring.


  • 0
    K

    @rahul8590

    This is how I thought about it:

    1. Let's say a valid string is 'abcabcabc'. Its pattern is 'abc', and then pattern repeats.
    2. I need to find this pattern ('abc'), and then check if the whole string follows the same pattern. I don't want to do a brute force check on this. What are my options?
    3. I use prefix in the code to find the 1st applicable pattern, then I make sure the suffix is also following the same pattern as the whole original string. I use 'str.startsWith(suffix)==true' to complete this check in my code.
    4. Why 'str.startsWith(suffix)==true' is enough? I could proof it by contradiction.
      Statement to prove:" If a given str is repetitive, then str.startsWith(suffix)==true"
      Proof by Contradiction: Let's say 'the str is repetitive', and 'str.startsWith(suffix)==false' is valid.
      But if 'str.startsWith(suffix)==false' (e.g. abacab), then 'str is not repetitive'
      So " If a given str is repetitive, then str.startsWith(suffix)==true"

Log in to reply
 

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