题目描述

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

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

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

子字符串 指的是字符串中一段连续 非空 的字符序列。

样例

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

输出：true

解释：

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

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

输出：false

解释：

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

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

输出：true

解释：

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

限制

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

算法

(暴力匹配) $O(nm)$

1. 先将模式串 $p$ 按照 * 进行分隔。
2. 通过内置的 find 函数，在 $s$ 中分别找到前半部分的最早出现位置，以及在这个位置之后能否匹配到后半部分。

时间复杂度

• 寻找 * 的时间复杂度为 $O(m)$。
• find 函数寻找的时间复杂度为 $O(nm)$。
• 故总时间复杂度为 $O(nm)$。
• 如果使用 KMP 算法，可以降低到 $O(n + m)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool hasMatch(string s, string p) {
        const int n = s.size(), m = p.size();
        int t = 0;
        while (p[t] != '*') ++t;

        auto l = s.find(p.substr(0, t));
        if (l == std::string::npos)
            return false;

        auto r = s.find(p.substr(t + 1), l + t);
        if (r == std::string::npos)
            return false;

        return true;
    }
};