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

2015-01-28 约 298 字预计阅读 1 分钟次阅读

力扣第 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 <= 10⁴
haystack 和 needle 仅由小写英文字符组成

分析

可以直接调包 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

目录

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

题目

分析

解答