2025-07-15：子字符串匹配模式。用go语言，给定一个字符串 s 和一个模式字符串 p，且 p 中恰好包含一个 '*' 字符。

'*' 可以代表任意长度（包括零）的任意字符序列。

如果通过替换 '*'，使得 p 变成 s 的一个子串，则返回 true，反之返回 false。

1 <= s.length <= 50。

1 <= p.length <= 50 。

s 只包含小写英文字母。

p 只包含小写英文字母和一个 '*' 符号。

输入：s = "leetcode", p = "ee*e"。

输出：true。

解释：

将 '*' 替换为 "tcod" ，子字符串 "eetcode" 匹配模式串。

题目来自力扣3407。

分步骤描述过程：

1. 理解题目要求：

o 给定字符串 s 和模式 p，p 中恰好包含一个 '*'。

o '*' 可以匹配任意长度（包括零）的任意字符序列。

o 需要通过替换 '*'，使得 p 变成 s 的一个子串。

2. 示例分析：

o s = "leetcode", p = "ee*e"：

o p 中的 '*' 将模式分为两部分："ee" 和 "e"。

o 需要在 s 中找到 "ee" 和 "e" 两部分，且 "ee" 在 "e" 之前，中间可以间隔任意字符。

3. 算法步骤：

o 步骤 1：定位 '*' 的位置：

o 在 p 中找到 '*' 的位置（star）。例如，p = "ee*e" 中 '*' 的位置是 2。

o 步骤 2：拆分模式：

o 将 p 拆分为 prefix（'*' 之前的部分）和 suffix（'*' 之后的部分）。

o prefix = p[:star] = "ee"。

o suffix = p[star+1:] = "e"。

o 步骤 3：查找 prefix 在 s 中的位置：

o 在 s 中查找 prefix 的第一个匹配位置（i）。

o s = "leetcode" 中 "ee" 的起始位置是 i = 1（子串 "ee" 从索引 1 开始）。

o 步骤 4：验证 suffix 的存在：

o 从 s 中 i + len(prefix) 的位置开始，检查 suffix 是否存在。

o i + len(prefix) = 1 + 2 = 3，即从索引 3 开始。

o s[3:] = "tcode"，检查 "e" 是否在其中："tcode" 包含 "e"（在 't' 之后）。

o 步骤 5：返回结果：

o 如果 prefix 和 suffix 都匹配，则返回 true；否则返回 false。

o 这里 prefix 和 suffix 都匹配，因此返回 true。

4. 边界情况：

o 如果 prefix 或 suffix 为空：

o prefix 为空：'*' 在模式开头，只需检查 suffix 是否是 s 的子串。

o suffix 为空：'*' 在模式末尾，只需检查 prefix 是否是 s 的子串。

o 如果 prefix 或 suffix 在 s 中不存在：

o 直接返回 false。

时间复杂度和空间复杂度：

o 时间复杂度：

• 定位 '*'：O(len(p))。
• 查找 prefix 在 s 中的位置：O(len(s) * len(prefix))（最坏情况）。
• 查找 suffix 在剩余部分的位置：O(len(s) * len(suffix))（最坏情况）。
• 总时间复杂度：O(len(s) * len(p))（因为 len(prefix) + len(suffix) = len(p) - 1）。

o 空间复杂度：

• 仅使用常数额外空间（存储 star、i 等变量），因此是 O(1)。

总结：

o 算法通过拆分模式并验证前后部分是否在字符串中依次出现，实现了子串匹配。

o 时间复杂度和字符串长度与模式长度乘积相关，空间复杂度为常数。

Go完整代码如下：

.

package main

import (
    "fmt"
    "strings"
)

func hasMatch(s, p string)bool {
    star := strings.IndexByte(p, '*')
    i := strings.Index(s, p[:star])
    return i >= 0 && strings.Contains(s[i+star:], p[star+1:])
}

func main() {
    s := "leetcode"
    p := "ee*e"
    result := hasMatch(s, p)
    fmt.Println(result)
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

def has_match(s: str, p: str) -> bool:
    star = p.index('*')
    i = s.find(p[:star])
    return i >= 0 and p[star+1:] in s[i+star:]

if __name__ == "__main__":
    s = "leetcode"
    p = "ee*e"
    result = has_match(s, p)
    print(result)

·

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展

·