0028. 实现 strStr()

0028. 实现 strStr() #

  • 标签:字符串、双指针
  • 难度:简单

题目大意 #

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置(从 0 开始)。如果不存在,则返回 -1。

解题思路 #

字符串匹配的经典题目。常见的字符串匹配算法有:BF(Brute Force)、RK(Robin-Karp)、KMP(Knuth Morris Pratt)、BM(Boyer Moore)、Sunday 算法等。

代码 #

  1. BF(Brute Force)暴力检索
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        i = 0
        j = 0
        len1 = len(haystack)
        len2 = len(needle)

        while i < len1 and j < len2:
            if haystack[i] == needle[j]:
                i += 1
                j += 1
            else:
                i = i - (j - 1)
                j = 0

        if j == len2:
            return i-j
        else:
            return -1
  1. RK(Robin-Karp)哈希检索
1

  1. KMP(Knuth Morris Pratt)算法
本站总访问量  次  |  您是本站第  位访问者