Java O(n^2) 15ms naive solution, one "if" make it much faster!


  • 1
    public boolean repeatedSubstringPattern(String str) {
        if(str.length()<=1) return false;
        int len = str.length();
        int right = 0;
        while(right<len/2){
            int sublen = right+1;
            if(len%sublen!=0||str.charAt(right)!=str.charAt(len-1)){//check the length of substring and the last character
                right++;
                continue;
            } 
            String sub = str.substring(0,sublen);
            int count = 1;
            while(true){
                String next = str.substring(count*sublen,(count+1)*sublen);
                if(!next.equals(sub)) break;
                count++;
                if(count*sublen>=len) return true;
            }
            right++;
        }
        return false;
    }

Log in to reply
 

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