Kimi LeetCode 3455. 最短匹配子字符串 Python3实现

LeetCode 3455. 最短匹配子字符串 — Python3 实现

题目概述

- 给定字符串 `s` 和模式串 `p`，`p` 中恰好包含两个 `'*'`。
- `'*'` 匹配零个或多个任意字符。
- 求 `s` 中匹配 `p` 的最短子串长度，不存在则返回 `-1`。
- 空子串是合法的（例如 `p = "**"` 时答案为 `0`）。

核心思路

将 `p` 按 `'*'` 分割为三部分：`left * mid * right`。

我们需要在 `s` 中找到：
1. `left` 的某个出现位置 `i`
2. `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) 版本）

```python
import math
from typing import List

class 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.inf
j = 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 += 1

if j == 0:
continue # 没有合法的 left

i1 = 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 += 1

if k == len(pos_right):
break # 后面的 mid 只会更大，right 更不可能满足

i3 = pos_right[k]

# 计算子串长度：[i1, i3 + len(right))
length = i3 + len(right) - i1
ans = min(ans, length)

return -1 if ans == math.inf else ans

def 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] * m
j = 0
for i in range(1, m):
while j > 0 and pattern[i] != pattern[j]:
j = lps[j - 1]
if pattern[i] == pattern[j]:
j += 1
lps[i] = j

# KMP 匹配
res = []
j = 0
for i in range(len(text)):
while j > 0 and text[i] != pattern[j]:
j = lps[j - 1]
if text[i] == pattern[j]:
j += 1
if 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`，即子串右端点（不包含）减去左端点。

---

验证示例

输入 输出 说明
`s="abaacbaecebce", p="ba*c*ce"` `8` 匹配 `"baecebce"`
`s="baccbaadbc", p="cc*baa*adb"` `-1` 无匹配
`s="a", p="**"` `0` 空串匹配
`s="madlogic", p="*adlogi*"` `6` 匹配 `"adlogi"`
`s="aa", p="aa**"` `2` `left="aa"`, `mid=""`, `right=""`，匹配 `"aa"`

---

参考来源

- 题解参考了 KMP + 双指针的 O(N) 实现思路
- 哞靠靠博客中对空模式串的处理技巧（返回 `N+1` 个索引）