Solution using KMP's Next Array


  • 0
    C
    public class Solution {
        public boolean repeatedSubstringPattern(String str) {
            int[] next = new int[str.length() + 1];
            int i = 1;
            int j = 0;
            while (i < str.length()){
                while(j > 0 && str.charAt(i) != str.charAt(j)) j = next[j];
                if (str.charAt(i) == str.charAt(j)) j++;
                next[++i] = j;
            }
            int strSubLen = str.length() - next[str.length()];
            if (strSubLen == str.length() || strSubLen > str.length() / 2) return false;
            for (i = strSubLen; i < str.length();){
                for (j = 0; j < strSubLen; i++, j++)
                    if (i >= str.length() || str.charAt(i) != str.charAt(j))
                        return false;
            }
            return true;
        }
    }
    

Log in to reply
 

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