O(m+n) and O(mn) solutions


  • 4
    G

    Solution 1: O(m+n) KMP pattern matching

     public int strStr(String haystack, String needle) {
            if(haystack == null || needle == null || needle.length() > haystack.length()) return -1;
            
            int[] parr = kmpPreprocess(needle);
            int i = 0, j = 0;
            while(i < haystack.length() && j < needle.length()) {
                if(haystack.charAt(i) == needle.charAt(j)) {
                    i++; j++;
                } else if(j > 0) {
                    j = parr[j - 1];
                } else {
                    i++;
                }
            }
            return j == needle.length() ? i - j : -1;
        }
    
        private int[] kmpPreprocess(String pattern) {
            int i = 1, j = 0;
            int[] res = new int[pattern.length()];
            while(i < pattern.length()) {
                if(pattern.charAt(i) == pattern.charAt(j)) {
                    res[i] = j+1;
                    i++; j++;
                } else if (j > 0) {
                    j = res[j-1];
                } else {
                    res[i] = 0;
                    i++;
                }
            }
            return res;
        }
    
    • If you want to understand KMP, watch the video.

    • KMP finds the pattern in a most efficient way. If the use cases require running multiple patterns then Rabin Karp algorithm may be useful.

    Solution 2: O(mn) Brute Force

     public int strStr(String haystack, String needle) {
            if(haystack == null || needle == null || needle.length() > haystack.length()) return -1;
    
            int len = haystack.length(), i = 0, j = 0, pos = 0;
            while(i < len && j < needle.length()) {
                if(haystack.charAt(i++) == needle.charAt(j)) {
                    j++;
                } else {
                    i = i - j;
                    j = 0;
                    pos = i;
                }
            }
            return j == needle.length()? pos : -1;
        }
    

  • 0
    B

    Thanks for sharing!


Log in to reply
 

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