3407. 子字符串匹配模式

English Version

题目描述

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

p 中的 '*' 符号可以被替换为零个或多个字符组成的任意字符序列。

如果 p 可以变成 s 的 子字符串，那么返回 true ，否则返回 false 。

 

示例 1：

示例 2：

示例 3：

 

提示：

• 1 <= s.length <= 50
• 1 <= p.length <= 50
• s 只包含小写英文字母。
• p 只包含小写英文字母和一个 '*' 符号。

解法

方法一：字符串匹配

根据题目描述，* 可以被替换为零个或多个字符组成的任意字符序列，因此我们可以将模式字符串 $p$ 按照 * 分割成若干个子串，如果这些子串依次出现在字符串 $s$ 中且顺序不变，则说明 $p$ 可以变成 $s$ 的子字符串。

因此，我们首先初始化一个指针 $i$ 指向字符串 $s$ 的起始位置，然后遍历模式字符串 $p$ 按照 * 分割得到的每个子串 $t$，在字符串 $s$ 中从位置 $i$ 开始查找子串 $t$，如果找到了，则将指针 $i$ 移动到子串 $t$ 的末尾位置继续查找下一个子串；如果找不到，则说明模式字符串 $p$ 不能变成字符串 $s$ 的子字符串，返回 $\text{false}$。如果所有子串都找到了，则返回 $\text{true}$。

时间复杂度 $O(n \times m)$，空间复杂度 $O(m)$。其中 $n$ 和 $m$ 分别是字符串 $s$ 和模式字符串 $p$ 的长度。

Python3

class Solution:
    def hasMatch(self, s: str, p: str) -> bool:
        i = 0
        for t in p.split("*"):
            j = s.find(t, i)
            if j == -1:
                return False
            i = j + len(t)
        return True

Java

class Solution {
    public boolean hasMatch(String s, String p) {
        int i = 0;
        for (String t : p.split("\\*")) {
            int j = s.indexOf(t, i);
            if (j == -1) {
                return false;
            }
            i = j + t.length();
        }
        return true;
    }
}

C++

class Solution {
public:
    bool hasMatch(string s, string p) {
        int i = 0;
        int pos = 0;
        int start = 0, end;
        while ((end = p.find("*", start)) != string::npos) {
            string t = p.substr(start, end - start);
            pos = s.find(t, i);
            if (pos == string::npos) {
                return false;
            }
            i = pos + t.length();
            start = end + 1;
        }
        string t = p.substr(start);
        pos = s.find(t, i);
        if (pos == string::npos) {
            return false;
        }
        return true;
    }
};

Go

func hasMatch(s string, p string) bool {
	i := 0
	for _, t := range strings.Split(p, "*") {
		j := strings.Index(s[i:], t)
		if j == -1 {
			return false
		}
		i += j + len(t)
	}
	return true
}

TypeScript

function hasMatch(s: string, p: string): boolean {
    let i = 0;
    for (const t of p.split('*')) {
        const j = s.indexOf(t, i);
        if (j === -1) {
            return false;
        }
        i = j + t.length;
    }
    return true;
}