3407. 子字符串匹配模式

题目描述

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

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

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

示例 1：

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

输出：true

解释：

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

示例 2：

输入：s = "car", p = "c*v"

输出：false

解释：

不存在匹配模式串的子字符串。

示例 3：

输入：s = "luck", p = "u*"

输出：true

解释：

子字符串 "u" ，"uc" 和 "uck" 都匹配模式串。

提示：

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\) 的长度。

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

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
}

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;
}

3407. 子字符串匹配模式

题目描述

解法

方法一：字符串匹配

评论