LeetCode 3455. 最短匹配子字符串 — Python3 实现题目概述- 给定字符串 s 和模式串 pp 中恰好包含两个 *。- * 匹配零个或多个任意字符。- 求 s 中匹配 p 的最短子串长度不存在则返回 -1。- 空子串是合法的例如 p ** 时答案为 0。核心思路将 p 按 * 分割为三部分left * mid * right。我们需要在 s 中找到1. left 的某个出现位置 i2. mid 的某个出现位置 j在 left 结束之后3. right 的某个出现位置 k在 mid 结束之后使得总长度 k len(right) - i 最小。方法KMP 双指针 / 二分查找步骤1. 用 KMP 找出 left、mid、right 在 s 中所有出现位置。2. 对于 mid 的每个出现位置用双指针或二分查找确定最优的 left 和 right。3. 空模式串特殊处理若某部分为空则认为每个位置都匹配返回 0, 1, 2, ..., n。复杂度- 时间O(|s| |p|)KMP 线性双指针扫描线性。- 空间O(|s| |p|)。---Python3 代码KMP 双指针 O(N) 版本pythonimport mathfrom typing import Listclass Solution:def shortestMatchingSubstring(self, s: str, p: str) - int:# 1. 分割模式串left, mid, right p.split(*)n len(s)# 2. KMP 找出所有出现位置pos_left self.kmp_all(s, left)pos_mid self.kmp_all(s, mid)pos_right self.kmp_all(s, right)# 3. 双指针找最短匹配ans math.infj 0 # pos_left 的指针k 0 # pos_right 的指针for i2 in pos_mid:# left 必须在 mid 开始之前结束i1 len(left) i2# 找满足条件的最后一个 left越靠右越好缩短总长度while j len(pos_left) and pos_left[j] len(left) i2:j 1if j 0:continue # 没有合法的 lefti1 pos_left[j - 1] # 最靠右的合法 left# right 必须在 mid 结束之后开始i3 i2 len(mid)# 找满足条件的第一个 right越靠左越好while k len(pos_right) and pos_right[k] i2 len(mid):k 1if k len(pos_right):break # 后面的 mid 只会更大right 更不可能满足i3 pos_right[k]# 计算子串长度[i1, i3 len(right))length i3 len(right) - i1ans min(ans, length)return -1 if ans math.inf else ansdef kmp_all(self, text: str, pattern: str) - List[int]:返回 pattern 在 text 中所有匹配的起始位置。如果 pattern 为空返回 [0, 1, ..., len(text)]每个位置都视为匹配if not pattern:return list(range(len(text) 1))# 计算前缀函数 (LPS / PMT)m len(pattern)lps [0] * mj 0for i in range(1, m):while j 0 and pattern[i] ! pattern[j]:j lps[j - 1]if pattern[i] pattern[j]:j 1lps[i] j# KMP 匹配res []j 0for i in range(len(text)):while j 0 and text[i] ! pattern[j]:j lps[j - 1]if text[i] pattern[j]:j 1if j m:res.append(i - m 1)j lps[j - 1]return res---代码说明部分 作用kmp_all 标准 KMP 算法返回所有匹配起始位置。空模式串返回 0..n这是处理 p ** 等边界情况的关键技巧。pos_left / pos_mid / pos_right 三部分在 s 中的所有出现位置列表天然有序。双指针循环 枚举 mid 的每个位置用 j 找最靠右的合法 left用 k 找最靠左的合法 right两者都是单调移动总复杂度 O(N)。长度计算 i3 len(right) - i1即子串右端点不包含减去左端点。---验证示例输入 输出 说明sabaacbaecebce, pba*c*ce 8 匹配 baecebcesbaccbaadbc, pcc*baa*adb -1 无匹配sa, p** 0 空串匹配smadlogic, p*adlogi* 6 匹配 adlogisaa, paa** 2 leftaa, mid, right匹配 aa---参考来源- 题解参考了 KMP 双指针的 O(N) 实现思路- 哞靠靠博客中对空模式串的处理技巧返回 N1 个索引