44. Wildcard Matching
給定一個輸入字符串 (s) 和一個模式 (p)，實現支持 '?' 和 '*' 的通配符模式匹配，其中：'?' 匹配任何單個字符。
'*' 匹配任何字符序列（包括空序列）。 匹配應覆蓋整個輸入字符串（不是部分匹配）。
範例 1：
輸入：s = "aa", p = "a" 輸出：false 解釋："a" 無法匹配整個字符串 "aa"。
Python
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
# dp[i][j] means s[:i] matches p[:j]
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
# Initialize the dp array for patterns with '*' at the beginning
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
# Fill the dp array
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
24.66MB, 411ms
C++
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
vector<vector<bool>> dp(m + 1, n + 1, false);
dp[0][0] = true;
// Initialize the dp array for patterns with '*' at the beginning
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
dp[0][j] = dp[0][j - 1];
}
}
// Fill the dp array
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
} else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
};
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[0][0] = true;
// Initialize the dp array for patterns with '*' at the beginning
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
dp[0][j] = dp[0][j - 1];
}
}
// Fill the dp array
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
} else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
};
15.49MB, 67ms
Javascript
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
const m = s.length, n = p.length;
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));
dp[0][0] = true;
// Initialize the dp array for patterns with '*' at the beginning
for (let j = 1; j <= n; ++j) {
if (p[j - 1] === '*') {
dp[0][j] = dp[0][j - 1];
}
}
// Fill the dp array
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
if (p[j - 1] === '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
} else if (p[j - 1] === '?' || s[i - 1] === p[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
};
66.49MB, 130ms
