my AC recursive solution 18ms(Java)


  • 0
    E
    public class Solution {
        int len = 0;
        public boolean repeatedSubstringPattern(String s) {
            len = s.length();
            if(len<2)return false;
            //a correct substring index must be start from 0 
            //so we define the starting index of substring as 0 and ending index as max
            //we recursively check it by increasing max
            return checkHelper(s,0);
        }
        
        boolean checkHelper(String s,int max){
            //if substring's ending index is greated thatn half of the given string return false
            if(max>=len)return false;
            //length of the substring must be divisor of the length of the given string 
            if(len%(max+1)!=0){
              return checkHelper(s,max+1);   
            }
            
            int index=0;
            for(int k=max+1;k<s.length();k++){
                if(index>max)index=0;
                //if does not mactch increa max by one
                if(s.charAt(k)!= s.charAt(index)){
                    return checkHelper(s,max+1);
                    
                }else{
                    index++;
                }                        
            }
            
            if(index>max)return true;
            
            return false;
        }
    }
    

Log in to reply
 

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