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

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. 1. 理解题目要求：
   • • 给定字符串 s 和模式 p，p 中恰好包含一个 '*'。
   • • '*' 可以匹配任意长度（包括零）的任意字符序列。
   • • 需要通过替换 '*'，使得 p 变成 s 的一个子串。
2. 2. 示例分析：
   • • s = "leetcode", p = "ee*e"：
     • • p 中的 '*' 将模式分为两部分："ee" 和 "e"。
     • • 需要在 s 中找到 "ee" 和 "e" 两部分，且 "ee" 在 "e" 之前，中间可以间隔任意字符。
3. 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. 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 >=  && strings.Contains(s[i+star:], p[star+:])
}

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 >=  and p[star+:] in s[i+star:]

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

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