当前位置:   article > 正文

LeetCode | 28.找出字符串中第一个匹配项的下标 KMP

LeetCode | 28.找出字符串中第一个匹配项的下标 KMP

在这里插入图片描述

这是字符串匹配问题,朴素做法是两重遍历,依次从主串的i位置开始查看是否和模式串匹配,若不匹配就换下一个位置进行判断,直到找到或者遍历完,时间复杂度 O ( m × n ) O(m \times n) O(m×n)
还可以对主串进行处理,把所有匹配模式串的字串替换为"1",然后在替换后的主串里面寻找第一个"1"出现的位置
但是这道题时间复杂度最低的还是得考虑用KMP算法,时间复杂度 O ( m + n ) O(m + n) O(m+n),这里我是看到Youtube上一位博主的讲解才恍然大悟的,链接在这里

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

    def getNext(self, needle):
        next = [0] * len(needle)
        j = 0
        for i in range(1, len(needle)):
            while j > 0 and needle[j] != needle[i]:
                j = next[j-1]
            if needle[j] == needle[i]:
                j += 1
            next[i] = j
        return next

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        restr = haystack.replace(needle, '1')
        for i in range(len(restr)):
            if restr[i] == '1':
                return i
        return -1
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46

在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/731786
推荐阅读
相关标签
  

闽ICP备14008679号