目录

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

力扣第 28 题

题目

给你两个字符串 haystackneedle ,请你在 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
  • haystackneedle 仅由小写英文字符组成

相似问题:

分析

可以直接调包 find。最优解是经典的 KMP 算法,能在线性时间内完成。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        def kmp(s):
            nxt, i = [-1], -1
            for c in s:
                while i>=0 and s[i]!=c:
                    i = nxt[i]
                i += 1
                nxt.append(i)
            return nxt   
        nxt = kmp(needle+'#'+haystack)
        n = len(needle)
        return -1 if n not in nxt else nxt.index(n)-2*n-1

48 ms