给你一个输入字符串 (s) 和一个字符模式 (p) ,请你实现一个支持 '?' 和 '' 匹配规则的通配符匹配: '?' 可以匹配任何单个字符。 '' 可以匹配任意字符序列(包括空字符序列)。 判定匹配成功的充要条件是:字符模式必须能够 完全匹配 输入字符串(而不是部分匹配)。
示例 1:
输入:s = "aa", p = "a"
输出:false
解释:"a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:s = "aa", p = "*"
输出:true
解释:'*' 可以匹配任意字符串。
示例 3:
输入:s = "cb", p = "?a"
输出:false
解释:'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
提示:
- 0 <= s.length, p.length <= 2000
- s 仅由小写英文字母组成
- p 仅由小写英文字母、'?' 或 '*' 组成
思路: 这个问题是一个典型的动态规划问题,我们可以通过比较字符串 s 和模式 p 中的字符来确定是否匹配。算法的关键在于处理*通配符,它可以匹配任意长度的字符序列。
- 初始化:我们使用两个指针 i 和 j 分别指向字符串 s 和模式 p 的当前位置。
- 逐个比较:从左到右逐个比较 s[i]和 p[j]。
- 处理?:如果 p[j]是?,或者 s[i]和 p[j]相同,那么两个指针都向前移动。
- 处理*:如果 p[j]是*,我们有两种情况:
- 如果*后面还有字符,我们尝试将*与后面的字符匹配,即移动 j 到下一个字符。
- 如果*后面没有字符,或者*可以匹配 0 个字符,我们尝试将*与前面的字符匹配,即移动 i 向前移动,同时记录*的位置 star 和当前 i 的位置 k。
- 回溯:如果当前字符不匹配,并且 p[j]不是*,那么返回 false。如果 p[j]是*,我们根据 star 和 k 回溯到*的前面,尝试匹配更多的字符。
- 结束条件:如果 i 已经遍历完 s,同时 j 也遍历完 p,那么返回 true。如果 i 遍历完 s,但 j 没有遍历完 p 且 p[j]不是*,那么返回 false。
时间复杂度是 O(n * m),其中 n 是字符串 s 的长度,m 是模式 p 的长度。这是因为在最坏的情况下,我们需要对每个 s 中的字符都尝试与 p 中的每个模式字符匹配。 空间复杂度是 O(1),因为除了输入字符串和模式之外,我们只需要常数个额外的变量。
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function (s, p) {
let i = 0;
let j = 0;
let star = -1;
let k = 0;
while (i < s.length) {
if (s[i] == p[j] || p[j] == '?') {
++i;
++j;
continue;
}
if (p[j] == '*') {
star = j++;
k = i;
continue;
}
if (star != -1) {
i = ++k;
j = star + 1;
continue;
}
return false;
}
while (j < p.length && p[j] == '*') ++j;
return j == p.length;
};