28.Implement strStr()

Tags: [string], [sub_string], [search], [shortcut], [trick]

Sub Tags: <KMP>

Com: {fb}

Link: https://leetcode.com/problems/implement-strstr/#/description

Implement strStr().

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

Solution: Shortcut

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if not needle:
            return 0
        if not haystack:
            return -1

        for i in xrange(len(haystack)):
            if haystack[i] != needle[0]:
                continue
            if len(haystack) - i < len(needle):
                return -1

            h_index = i
            n_index = 0
            is_match = True
            while h_index < len(haystack) and n_index < len(needle):
                if haystack[h_index] != needle[n_index]:
                    is_match = False
                    break
                h_index += 1
                n_index += 1

            if is_match and n_index == len(needle):
                return i

        return -1

Revelation:

• To make the algorithm a little more faster (time complexity doesn't change), we add the following code, to terminate the loop early.

if len(haystack) - i < len(needle):
    return -1

• Do not forget to check 'n_index == len(needle)' after the inner while loop.

if is_match and n_index == len(needle):
    return i

Note:

• Time complexity = O(len(haystack) * len(needle)).
• Space complexity = O(1).

Here is a good explanation of KMP algorithm: http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/