[ LeetCode ] 题刷刷(Python)-第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 。

解题

解法一： 内置函数str.find()方法

思路

有点不讲武德，但是第一反应就想到这个方法了。

算法复杂度

时间复杂度：O(n)，其中 n 是 haystack 的长度。

空间复杂度：O(1)，即常数空间复杂度。

代码

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.find(needle)

解法二： 暴力破解

思路

从 haystack 的每个字符开始，依次比较后续字符是否与 needle 相同，直到找到匹配项或遍历完所有可能的起始位置。

算法复杂度

时间复杂度：O(n*m)，其中 n 是 haystack 的长度，m 是 needle 的长度。

空间复杂度：O(1)，即常数空间复杂度。

代码

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        for i in range(len(haystack) - len(needle) + 1):  # 遍历所有可能的起始位置
            if haystack[i:i+len(needle)] == needle:  # 完全匹配 needle
                return i  # 返回 needle 在 haystack 中的起始位置

        return -1  # 未找到 needle，返回 -1

解法三： KMP算法

思路

从 haystack 的每个字符开始，依次比较后续字符是否与 needle 相同，直到找到匹配项或遍历完所有可能的起始位置。

原理找个视频看一下，手工推算，然后尝试写成代码。

算法复杂度

时间复杂度：O(n+m)，其中 n 是 haystack 的长度，m 是 needle 的长度。

空间复杂度：O(m)，其中m 是 needle 的长度。

代码

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # 如果 needle 为空字符串，其在 haystack 中的起始位置为 0
        if not needle:
            return 0
        
        # 构建 KMP 部分匹配表（LPS）
        lps = self._get_lps(needle)
        
        # 初始化双指针 i 和 j 分别指向 haystack 和 needle 的起始位置
        i, j = 0, 0
        
        # 当 i 未到达 haystack 的末尾时，继续搜索
        while i < len(haystack):
            # 如果当前字符匹配，移动两个指针到下一个字符
            if haystack[i] == needle[j]:
                i += 1
                j += 1
                
                # 如果 j 到达 needle 的末尾，说明找到了完整的 needle，返回其在 haystack 中的起始位置
                if j == len(needle):
                    return i - j
            
            # 如果当前字符不匹配且 j > 0，利用 LPS 表回退 j 指针至下一个最长前后缀重合位置
            elif j > 0:
                j = lps[j - 1]
            
            # 如果当前字符不匹配且 j == 0，说明 needle 无法在当前位置继续匹配，i 指针右移一位
            else:
                i += 1
                
        # 若遍历完 haystack 仍未找到 needle，返回 -1 表示未找到
        return -1

    # 私有辅助方法，用于生成 KMP 部分匹配表
    def _get_lps(self, pattern: str) -> List[int]:
        # 初始化长度为 pattern 长度的 LPS 表，初始值均为 0
        lps = [0] * len(pattern)
        
        # 初始化 j 指针指向 pattern 的第二个字符
        j = 0
        
        # 从 pattern 的第二个字符开始遍历，直至最后一个字符
        for i in range(1, len(pattern)):
            # 当 j > 0 且 pattern[i] 与 pattern[j] 不匹配时，回退 j 至 LPS 表中对应的前一位置
            while j > 0 and pattern[i] != pattern[j]:
                j = lps[j - 1]
            
            # 当 pattern[i] 与 pattern[j] 匹配时，将 j 向右移动一位
            if pattern[i] == pattern[j]:
                j += 1
            
            # 更新 LPS 表中对应位置的值为当前 j 的值
            lps[i] = j
        
        # 返回计算好的 LPS 表
        return lps