2025-07-15：子字符串匹配模式。用go语言，给定一个字符串 s 和一

大家好，欢迎来到IT知识分享网。

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. 理解题目要求：

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

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

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

2. 示例分析：

• s = “leetcode”, p = “ee*e”：

• p 中的 ‘*’ 将模式分为两部分：“ee” 和 “e”。

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

3. 算法步骤：

• 步骤 1：定位 ‘*’ 的位置：

• 在 p 中找到 ‘*’ 的位置（star）。例如，p = “ee*e” 中 ‘*’ 的位置是 2。

• 步骤 2：拆分模式：

• 将 p 拆分为 prefix（‘*’ 之前的部分）和 suffix（‘*’ 之后的部分）。

• prefix = p[:star] = “ee”。

• suffix = p[star+1:] = “e”。

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

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

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

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

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

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

• s[3:] = “tcode”，检查 “e” 是否在其中：“tcode” 包含 “e”（在 ‘t’ 之后）。

• 步骤 5：返回结果：

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

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

4. 边界情况：

• 如果 prefix 或 suffix 为空：

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

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

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

• 直接返回 false。

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

• 时间复杂度：

• 定位 ‘*’：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）。

• 空间复杂度：

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

总结：

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

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

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 语言和算法助力您的职业发展

·