Java solution O(N) using KMP


  • 0
    G
    public class Solution {
        public boolean repeatedSubstringPattern(String s) {
            
            if(s.isEmpty()){
                return true;
            }
            
            int [] kmp = new int[s.length()];
            char [] arr = s.toCharArray();
            int i = 0,j = 1;
            
            while(j < arr.length){
                if(arr[j] == arr[i]){
                    kmp[j] = i + 1;
                    i++;
                    j++;
                }
                else{
                    
                    if(i == 0){
                        j++;
                    }
                    else{
                        i = kmp[i - 1];
                    }
                }
            }
            
            String temp = s.substring(i);        
            return (i != 0 && temp.equals(s.substring(0,j - i)));
            
        }
    }

Log in to reply
 

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