LeetCode 28. Implement strStr() 题解

LeetCode 28. Implement strStr() 题解题目描述实现strStr()函数。给你两个字符串haystack和needle请你在haystack字符串中找出needle字符串出现的第一个位置下标从 0 开始。如果不存在则返回-1。示例 1输入haystack hello, needle ll 输出2示例 2输入haystack aaaaa, needle bba 输出-1解题思路暴力解法遍历 haystack对于每个位置检查是否以该位置开始的子串等于 needleKMP 算法预处理 needle构建部分匹配表next 数组利用 next 数组加速匹配过程代码实现方法一暴力解法def strStr(haystack, needle): n len(haystack) m len(needle) if m 0: return 0 for i in range(n - m 1): if haystack[i:im] needle: return i return -1方法二KMP 算法def strStr(haystack, needle): n len(haystack) m len(needle) if m 0: return 0 # 构建 next 数组 next_arr [0] * m j 0 for i in range(1, m): while j 0 and needle[i] ! needle[j]: j next_arr[j-1] if needle[i] needle[j]: j 1 next_arr[i] j # KMP 匹配 j 0 for i in range(n): while j 0 and haystack[i] ! needle[j]: j next_arr[j-1] if haystack[i] needle[j]: j 1 if j m: return i - m 1 return -1复杂度分析方法时间复杂度空间复杂度暴力O(nm)O(1)KMPO(nm)O(m)测试案例# 测试案例 1 assert strStr(hello, ll) 2 # 测试案例 2 assert strStr(aaaaa, bba) -1 # 测试案例 3 assert strStr(, ) 0 # 测试案例 4 assert strStr(a, a) 0总结本题是字符串匹配的经典问题。关键点暴力解法的简单实现KMP 算法的优化边界条件处理通过本题可以深入理解字符串匹配算法。