28. Implement strStr()

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

Solution

(1) Java

class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null) {
            return -1;
        }
        if (needle.length() == 0) {
            return 0;
        }
        int len = needle.length();
        int[] next = new int[len];
        getNext(needle, next);
        int i = 0;
        int j = 0;
        while (i < haystack.length() && j < needle.length()) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
                if (j == len) {
                    return i-len;
                }
            } else if (j == 0) {
                i++;
            } else {
                j = next[j-1];
            }            
        }
        return -1;
    }

    private void getNext(String needle, int[] next) {
        int i = 0;
        int j = 1;
        while (i < next.length && j < next.length) {
            if (needle.charAt(i) == needle.charAt(j)) {
                i++;
                next[j] = i;
                j++;
            } else if (i == 0) {
                j++;
            } else {
                i = next[i-1];
            }
        }
    }
}

(2) Python

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        def getNext():
            i, j, l = 0, 1, len(needle)
            while i < l and j < l:
                if needle[i] == needle[j]:
                    i += 1
                    next[j] = i
                    j += 1
                elif i == 0:
                    j += 1
                else:
                    i = next[i-1]

        if not needle:
            return 0
        next = [0]*len(needle)
        getNext()
        i, j, l = 0, 0, len(haystack)
        while i < l and j < l:
            if haystack[i] == needle[j]:
                i += 1
                j += 1
                if j == len(needle):
                    return i - len(needle)
            elif j == 0:
                i += 1
            else:
                j = next[j-1]
        return -1

(3) Scala

object Solution {
    def strStr(haystack: String, needle: String): Int = {
        if (haystack == null || needle == null) {
            return -1
        }
        if (needle.length() == 0) {
            return 0
        }
        var next = new Array[Int](needle.length())
        getNext(needle, next)
        var i = 0
        var j = 0
        val l = haystack.length()
        while (i < l && j < l) {
            if (haystack(i) == needle(j)) {
                i += 1
                j += 1
                if (j == needle.length()) {
                    return i - needle.length();
                }
            } else if (j == 0) {
                i += 1
            } else {
                j = next(j-1)
            }
        }
        return -1
    }

    def getNext(needle: String, next: Array[Int]) {
        var i = 0
        var j = 1
        val l = needle.length()
        while (i < l && j < l) {
            if (needle(i) == needle(j)) {
                i += 1
                next(j) = i
                j += 1
            } else if (i == 0) {
                j += 1
            } else {
                i = next(i-1)
            }
        }
    }
}