Java O(n) solution without KMP


  • 0
    public class Solution {
        
        public boolean repeatedSubstringPattern(String s)
        {
            return repeatedSubstringPatternHelper(s) || repeatedSubstringPatternHelper(new StringBuffer(s).reverse().toString());
        }
        
        public boolean repeatedSubstringPatternHelper(String s)
    	{
    		int len = s.length();
    		int ptr1 = 0,
    			ptr2 = 1;
    
    		while(ptr2 < len)
    		{
    			if(s.charAt(ptr1) != s.charAt(ptr2))
    				ptr1 = 0;
    
    			if(s.charAt(ptr1) == s.charAt(ptr2))
    			    ptr1++;
    
    			ptr2++;
    		}
    	
    		
    		return len > 0 && checkLastSubstring(s,len,ptr1);
    	}
    
    	public boolean checkLastSubstring(String s,int len,int ptr1)
    	{
    
    		if((len - ptr1) > ptr1)
    			return false;
    
    		int ptr2 = 0;
    
    		while(ptr1 < len)
    		{
    			if(s.charAt(ptr2) != s.charAt(ptr1))
    				return false;
    			ptr1++;
    			ptr2++;
    		}
    
    		return true;
    	}
    }
    

Log in to reply
 

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