Leetcode第28题：实现 strStr()【python】

本文主要是介绍Leetcode第28题：实现 strStr()【python】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅
python数据分析可视化：企业实战案例
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级

问题描述

实现 strStr() 函数。给你两个字符串 haystack 和 needle，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1。

说明：

• 当 needle 是空字符串时，我们应返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例

输入： haystack = "hello", needle = "ll"

输出： 2

输入： haystack = "aaaaa", needle = "bba"

输出： -1

解题思路

实现 strStr() 函数的方法多种多样，包括暴力匹配法、KMP算法、Rabin-Karp 算法等。下面分别简述这些方法：

1. 暴力匹配法

暴力匹配法是最直接的方法，它遍历 haystack 中的每个子串，检查子串是否与 needle 相等。

算法步骤

• 遍历从 0 到 len(haystack) - len(needle) 的每一个起始位置。
• 对每一个起始位置，比较后续的 len(needle) 个字符是否与 needle 相等。

代码实现

这里提供暴力匹配法的实现：

def strStr(haystack: str, needle: str) -> int:"""实现 strStr() 函数。Args:haystack (str): 主字符串，从中搜索子字符串。needle (str): 子字符串，需要在主字符串中找到其第一次出现的位置。Returns:int: 子字符串在主字符串中第一次出现的索引；如果不存在，则返回 -1。"""# 特殊情况处理if not needle:return 0if not haystack:return -1# 获取主字符串和子字符串的长度L, n = len(needle), len(haystack)# 只在主字符串长度减去子字符串长度的范围内搜索for start in range(n - L + 1):# 检查从start开始的长度为L的子串是否等于needleif haystack[start:start + L] == needle:return startreturn -1# 调用函数示例
haystack = "hello"
needle = "ll"
print(strStr(haystack, needle))  # 输出: 2haystack = "aaaaa"
needle = "bba"
print(strStr(haystack, needle))  # 输出: -1

复杂度分析：

• 时间复杂度：O((N-M)M)，其中 N 是 haystack 的长度，M 是 needle 的长度。
• 空间复杂度：O(1)。

2. KMP 算法（Knuth-Morris-Pratt）

算法步骤

KMP算法的核心思想是当发生不匹配时，能够利用已匹配的部分信息，确定模式串的哪个部分应该重新进行匹配，从而避免从头开始匹配。

构建前缀表：

• 前缀表记录了模式串中每个位置之前的子串的前缀与后缀的最长共有元素的长度。
• 这个表用于在发生不匹配时，确定模式串应该回溯到哪个位置重新开始匹配。

搜索过程：

• 使用前缀表来调整模式串的位置，减少不必要的比较。
• 当发生不匹配时，根据前缀表中记录的值调整模式串的位置。

代码实现

def kmp_search(haystack: str, needle: str) -> int:"""实现 KMP 算法进行字符串搜索。Args:haystack (str): 主字符串，从中搜索子字符串。needle (str): 子字符串，需要在主字符串中找到其第一次出现的位置。Returns:int: 子字符串在主字符串中第一次出现的索引；如果不存在，则返回 -1。"""if not needle:return 0if not haystack:return -1# 构建前缀表lps = build_lps(needle)i = j = 0  # i 是 haystack 的指针，j 是 needle 的指针while i < len(haystack):if haystack[i] == needle[j]:i += 1j += 1if j == len(needle):return i - jelif j > 0:j = lps[j - 1]else:i += 1return -1def build_lps(needle: str) -> list:"""构建前缀表 (Longest Prefix which is also Suffix table) 用于 KMP 算法。Args:needle (str): 需要构建前缀表的字符串。Returns:list: 前缀表。"""lps = [0] * len(needle)length = 0  # 最长前缀后缀的长度i = 1       # lps[0] 是 0，从 lps[1] 开始填充表while i < len(needle):if needle[i] == needle[length]:length += 1lps[i] = lengthi += 1else:if length != 0:length = lps[length - 1]else:lps[i] = 0i += 1return lps# 调用函数示例
haystack = "hello"
needle = "ll"
print(kmp_search(haystack, needle))  # 输出: 2haystack = "aaaaa"
needle = "bba"
print(kmp_search(haystack, needle))  # 输出: -1

复杂度分析

• 时间复杂度：O(N+M)，预处理时间为 O(M)，匹配时间为 O(N)。
• 空间复杂度：O(M)。

3. Rabin-Karp 算法

Rabin-Karp 算法是一种高效的字符串搜索算法，特别适用于多模式搜索。它通过计算字符串的哈希值来快速筛选可能的匹配，从而避免在每一步都进行详细的字符比较。

算法步骤

哈希函数：

• 选择一个合适的哈希函数来计算字符串的哈希值。常用的方法是将字符串视为一个大的数值，计算它模一个大素数的值。

计算 needle 的哈希值：

• 计算模式串（needle）的哈希值。

计算 haystack 子串的哈希值并比较：

• 逐步计算主字符串（haystack）中每个长度与 needle 相等的子串的哈希值。
• 如果哈希值匹配，则进行进一步的字符比较以确认完全匹配。

滚动哈希：

• 为了有效计算连续子串的哈希值，使用滚动哈希技术，根据前一个哈希值快速计算下一个哈希值。

def rabin_karp_search(haystack: str, needle: str) -> int:"""实现 Rabin-Karp 算法进行字符串搜索。Args:haystack (str): 主字符串，从中搜索子字符串。needle (str): 子字符串，需要在主字符串中找到其第一次出现的位置。Returns:int: 子字符串在主字符串中第一次出现的索引；如果不存在，则返回 -1。"""M, N = len(needle), len(haystack)if M > N:return -1if not needle:return 0# 基数和模块数（大素数以减少冲突）base, mod = 256, 997# 计算needle的哈希值和第一个窗口的哈希值hash_needle, hash_window = 0, 0for i in range(M):hash_needle = (hash_needle * base + ord(needle[i])) % modhash_window = (hash_window * base + ord(haystack[i])) % mod# 如果只有一个字符，直接比较初值if hash_needle == hash_window:if haystack[:M] == needle:return 0# 预计算base^(M-1) % modpower_base = 1for i in range(M - 1):power_base = (power_base * base) % mod# 滚动哈希：遍历剩余的窗口for i in range(1, N - M + 1):hash_window = (hash_window * base - ord(haystack[i - 1]) * power_base + ord(haystack[i + M - 1])) % modif hash_window < 0:hash_window += modif hash_window == hash_needle:# 验证实际字符串是否匹配if haystack[i:i + M] == needle:return ireturn -1# 调用函数示例
haystack = "hello"
needle = "ll"
print(rabin_karp_search(haystack, needle))  # 输出: 2haystack = "aaaaa"
needle = "bba"
print(rabin_karp_search(haystack, needle))  # 输出: -1

复杂度分析：

• 平均时间复杂度：O(N+M)。
• 最坏情况下的时间复杂度：O(NM)，当所有哈希值都冲突时。
• 空间复杂度：O(1)。

总结

下面是对暴力匹配法、KMP算法、以及Rabin-Karp算法在实现 strStr() 函数时的优势、劣势及其时间复杂度和空间复杂度的对比表格，这将帮助在不同场景下选择最适合的方法。

这篇关于Leetcode第28题：实现 strStr()【python】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---