# 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'.
``````

Example 4:

``````Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
``````

Example 5:

``````Input:
s = "acdcb"
p = "a*c?b"
Output: false
``````

Constraints:

• `0 <= s.length, p.length <= 2000`
• `s` contains only lowercase English letters.
• `p` contains only lowercase English letters, `'?'` or `'*'`.

``````class Solution {
public:
bool isMatch(string s, string p) {
int i = 0, j = 0, iStar = -1, jStar = -1, m = s.size(), n = p.size();
while (i < m) {
if (j < n && (s[i] == p[j] || p[j] == '?')) {
++i; ++j;
} else if (j < n && p[j] == '*') {
iStar = i;
jStar = j++;
} else if (iStar >= 0) {
i = ++iStar;
j = jStar + 1;
} else return false;
}
while (j < n && p[j] == '*') ++j;
return j == n;
}
};
``````

``````class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
dp[0][0] = true;
for (int i = 1; i <= n; ++i) {
if (p[i - 1] == '*') dp[0][i] = dp[0][i - 1];
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
} else {
dp[i][j] = (s[i - 1] == p[j - 1] || p[j - 1] == '?') && dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
};
``````

``````class Solution {
public:
bool isMatch(string s, string p) {
return helper(s, p, 0, 0) > 1;
}
int helper(string& s, string& p, int i, int j) {
if (i == s.size() && j == p.size()) return 2;
if (i == s.size() && p[j] != '*') return 0;
if (j == p.size()) return 1;
if (s[i] == p[j] || p[j] == '?') {
return helper(s, p, i + 1, j + 1);
}
if (p[j] == '*') {
if (j + 1 < p.size() && p[j + 1] == '*') {
return helper(s, p, i, j + 1);
}
for (int k = 0; k <= (int)s.size() - i; ++k) {
int res = helper(s, p, i + k, j + 1);
if (res == 0 || res == 2) return res;
}
}
return 1;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/44

Regular Expression Matching

https://leetcode.com/problems/wildcard-matching/

https://leetcode.com/problems/wildcard-matching/discuss/17839/C%2B%2B-recursive-solution-16-ms

https://leetcode.com/problems/wildcard-matching/discuss/17910/clear-c-dp-solution-similar-to-the-last-matching-problem

https://leetcode.com/problems/wildcard-matching/discuss/17811/My-three-C%2B%2B-solutions-(iterative-(16ms)-and-DP-(180ms)-and-modified-recursion-(88ms))

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation