题目描述
给你两个字符串
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)，即常数空间复杂度。
代码
python">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)，即常数空间复杂度。
代码
python">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: # 完全匹配 needlereturn i # 返回 needle 在 haystack 中的起始位置return -1 # 未找到 needle，返回 -1解法三： KMP算法
思路
从 haystack 的每个字符开始，依次比较后续字符是否与 needle 相同，直到找到匹配项或遍历完所有可能的起始位置。
原理找个视频看一下，手工推算，然后尝试写成代码。
算法复杂度
时间复杂度：O(n+m)，其中 n 是 haystack 的长度，m 是 needle 的长度。
空间复杂度：O(m)，其中m 是 needle 的长度。
代码
python">class Solution:def strStr(self, haystack: str, needle: str) -> int:# 如果 needle 为空字符串，其在 haystack 中的起始位置为 0if 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 += 1j += 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 表，初始值均为 0lps = [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
