如何优化LeetCode字符串匹配问题的代码运行时间？

问题描述 #

给定两个字符串needle和haystack，返回needle在haystack中首次出现的索引；若needle不在haystack中，则返回-1。

示例

• 输入：haystack = "sadbutsad", needle = "sad"
  输出：0
• 输入：haystack = "leetcode", needle = "leeto"
  输出：-1

原始代码 #

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle not in haystack:
            return -1 
        else:
            for i in range (0, (len(haystack)-len(needle))+1):
                if haystack[i:i+len(needle)] == needle:
                    return i
                    break

优化方案 #

你的代码现在做了两次重复的字符串匹配：一次是needle not in haystack的检查，一次是循环里的子串比对，这会额外消耗性能。直接去掉前置的存在性检查，把匹配逻辑合并到一次循环里，就能减少不必要的遍历。另外，针对空串等特殊情况提前处理，还能避免后续计算出错。

基础优化版本（暴力匹配优化）

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n_len = len(needle)
        h_len = len(haystack)
        
        # 处理空串特殊情况，符合原题要求
        if n_len == 0:
            return 0
        
        # 只遍历到可能的最后一个起始位置
        for i in range(h_len - n_len + 1):
            # 逐字符比对，避免切片创建新字符串的开销
            match = True
            for j in range(n_len):
                if haystack[i+j] != needle[j]:
                    match = False
                    break
            if match:
                return i
        # 未找到匹配返回-1
        return -1

进阶优化：KMP算法（针对大字符串场景）

如果要处理极大长度的字符串，暴力匹配最坏时间复杂度是O(m*n)（m为haystack长度，n为needle长度），用KMP算法可以把时间复杂度降到O(m+n)。核心是通过预处理needle生成前缀函数，避免匹配失败时回溯haystack的指针：

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n_len = len(needle)
        h_len = len(haystack)
        
        if n_len == 0:
            return 0
        
        # 生成前缀函数数组，记录最长相等前后缀长度
        prefix = [0] * n_len
        j = 0
        for i in range(1, n_len):
            while j > 0 and needle[i] != needle[j]:
                j = prefix[j-1]
            if needle[i] == needle[j]:
                j += 1
                prefix[i] = j
        
        # KMP匹配过程
        j = 0
        for i in range(h_len):
            while j > 0 and haystack[i] != needle[j]:
                j = prefix[j-1]
            if haystack[i] == needle[j]:
                j += 1
            if j == n_len:
                return i - n_len + 1
        return -1

优化说明 #

1. 移除重复检查：原代码的needle not in haystack内部会做一次完整遍历，和后续循环重复，合并后只需要一次遍历即可完成匹配和判断。
2. 替换切片为逐字符比对：切片操作会创建新字符串对象，逐字符比对能节省内存和对象创建的开销。
3. 特殊情况前置处理：提前处理空串，符合LeetCode原题的隐含要求。
4. KMP算法优化：针对大字符串场景，避免暴力匹配的最坏情况，大幅提升匹配效率。

内容的提问来源于stack exchange，提问作者Siddharth Mody