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` 个索引）