力扣代码学习日记二-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣代码学习日记二。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Problem: 28. 找出字符串中第一个匹配项的下标

思路

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成

解题方法

可以使用 Python 内置的字符串方法 find() 来实现这个功能。find() 方法返回子字符串在字符串中第一次出现的位置，如果没有找到则返回 -1。

KMP算法

复杂度

时间复杂度:

O(N*M)，其中 N 是字符串 haystack 的长度，M 是字符串 needle 的长度。在最坏的情况下，即 needle 与 haystack 的每个子串都几乎相同，但最后一个字符不匹配时，需要对 haystack 的每个位置都尝试匹配 needle，并且每次匹配都需要比较 M 个字符。

空间复杂度:

O(1)。使用 find() 方法进行搜索不需要额外的存储空间，所需空间不随输入数据的大小而改变，因此是常数级别的。

代码

class Solution(object):
    def strStr(self, haystack, needle):
        return haystack.find(needle)

使用KMP算法（目前能力还看不懂）

class Solution(object):
    def strStr(self, haystack, needle):
        if not needle:
            return 0
    
        def build_lps(pattern):
            lps = [0] * len(pattern)
            j = 0
            for i in range(1, len(pattern)):
                while j > 0 and pattern[i] != pattern[j]:
                    j = lps[j - 1]
                if pattern[i] == pattern[j]:
                    j += 1
                lps[i] = j
            return lps
    
        lps = build_lps(needle)
        j = 0
        for i in range(len(haystack)):
            while j > 0 and haystack[i] != needle[j]:
                j = lps[j - 1]
            if haystack[i] == needle[j]:
                j += 1
            if j == len(needle):
                return i - j + 1
        return -1