44. Wildcard Matching
44. Wildcard Matching
题目
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:
'?'Matches any single character.'*'Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.
Example 3:
Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Constraints:
0 <= s.length, p.length <= 2000scontains only lowercase English letters.pcontains only lowercase English letters,'?'or'*'.
题目大意
给定一个输入字符串 (s) 和一个模式 (p)，请实现通配符匹配，支持 ? 和 *。
?可以匹配任何单个字符。*可以匹配任意字符串（包括空字符串）。
匹配应该覆盖整个输入字符串（而不是部分匹配）。
解题思路
这个问题可以使用动态规划来解决，具体思路如下：
定义状态：
dp[i][j]表示字符串s的前i个字符是否能够匹配模式p的前j个字符。初始化状态：
dp[0][0]表示空字符串匹配空模式，为True；dp[i][0]表示空模式，不管字符串s有多长，都为False。状态转移方程：
当
p[j-1]是普通字符且当前字符匹配时，dp[i][j] = dp[i-1][j-1]，表示结果与之前状态相同。当
p[j-1]是'*'时，dp[i][j]可以通过以下三种情况获得：- 匹配零个字符：
dp[i][j] = dp[i][j-1] - 匹配一个字符：
dp[i][j] = dp[i-1][j-1] - 匹配多个字符：
dp[i][j] = dp[i-1][j]
- 匹配零个字符：
最终返回
dp[m][n]，其中m和n分别是字符串s和模式p的长度。
这个算法的时间复杂度和空间复杂度都是 O(m * n)，其中 m 和 n 分别是字符串 s 和模式 p 的长度。
代码
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function (s, p) {
const m = s.length;
const n = p.length;
const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(false));
// 空字符串和空模式匹配
dp[0][0] = true;
// 初始化 dp[0][j]，处理 p 中可能出现 '*' 的情况
for (let j = 1; j <= n; j++) {
if (p[j - 1] == '*') {
dp[0][j] = dp[0][j - 1];
}
}
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s[i - 1] == p[j - 1] || p[j - 1] == '?') {
dp[i][j] = dp[i - 1][j - 1];
} else if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j] || dp[i - 1][j - 1];
}
}
}
return dp[m][n];
};