0028._implement_strstr().md

28. Implement strStr()

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/implement-strstr/description/

内容描述

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().

解题方案

思路 1 - 时间复杂度: O(m * n)- 空间复杂度: O(1)******

• m = len(haystack)
• n = len(needle)

作弊，python str.find() 底层实现是 Boyer–Moore–Horspool 算法

The time complexity is O(N) on average, O(NM) worst case (N being the length of the longer string, M, the shorter string you search for).

Runtime of python's if substring in string

beats 100%

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        return haystack.find(needle)

思路 2 - 时间复杂度: O(m * n)- 空间复杂度: O(1)******

这个题目其实可以引来一大类，那就是关于string的算法，但是此处先用暴力算法来AC，然后再来细读/品味别的string相关算法吧。

虽然是暴力算法，但是也不容易写对啊

beats 67.60%

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if not needle or len(needle) == 0:
            return 0
        for i in range(len(haystack)-len(needle)+1):
            if haystack[i] == needle[0]:
                j = 1
                while j < len(needle) and haystack[i+j] == needle[j]:
                    j += 1
                if j == len(needle):
                    return i
        return -1

思路 3 - 时间复杂度: O(m + n)- 空间复杂度: O(n)******

beats 25.41%, 这可能跟test case有关，case多一些长一些就是KMP更快了

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """ 
        text, pattern = haystack, needle
        if not pattern or len(pattern) == 0:
            return 0
        
        lps = self.findLPS(pattern) # longest proper prefix which is also suffix
        i, j = 0, 0 # idx for text and pattern
        res = -1
        while i < len(text):
            if pattern[j] == text[i]:
                i += 1
                j += 1
            if j == len(pattern):
                res = i - j
                return res
                j = lps[j-1]
            elif i < len(text) and pattern[j] != text[i]: # mismatch after j matches 
                if j != 0: # Don't match lps[0..lps[j-1]] characters, they will match anyway 
                    j = lps[j-1]
                else:
                    i += 1  
        return res

    def findLPS(self, pattern): 
        length, lps = 0, [0]
        for i in range(1, len(pattern)):
            while length > 0 and pattern[length] != pattern[i]:
                length = lps[length-1]
            if pattern[length] == pattern[i]:
                length += 1
            lps.append(length)
        return lps