## Wildcard Matching

• Time:O(|\texttt{s}||\texttt{p}|)
• Space:O(|\texttt{s}||\texttt{p}|)

## C++

``````class Solution {
public:
bool isMatch(string s, string p) {
const int m = s.length();
const int n = p.length();
// dp[i][j] := true if s[0..i) matches p[0..j)
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
dp[0][0] = true;

auto isMatch = [&](int i, int j) -> bool {
return j >= 0 && p[j] == '?' || s[i] == p[j];
};

for (int j = 0; j < p.length(); ++j)
if (p[j] == '*')
dp[0][j + 1] = dp[0][j];

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (p[j] == '*') {
const bool matchEmpty = dp[i + 1][j];
const bool matchSome = dp[i][j + 1];
dp[i + 1][j + 1] = matchEmpty || matchSome;
} else if (isMatch(i, j)) {
dp[i + 1][j + 1] = dp[i][j];
}

return dp[m][n];
}
};
``````

## JAVA

``````class Solution {
public boolean isMatch(String s, String p) {
final int m = s.length();
final int n = p.length();
// dp[i][j] := true if s[0..i) matches p[0..j)
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;

for (int j = 0; j < p.length(); ++j)
if (p.charAt(j) == '*')
dp[0][j + 1] = dp[0][j];

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (p.charAt(j) == '*') {
final boolean matchEmpty = dp[i + 1][j];
final boolean matchSome = dp[i][j + 1];
dp[i + 1][j + 1] = matchEmpty || matchSome;
} else if (isMatch(s, i, p, j)) {
dp[i + 1][j + 1] = dp[i][j];
}

return dp[m][n];
}

private boolean isMatch(final String s, int i, final String p, int j) {
return j >= 0 && p.charAt(j) == '?' || s.charAt(i) == p.charAt(j);
}
}
``````

## Python

``````class Solution:
def isMatch(self, s: str, p: str) -> bool:
m = len(s)
n = len(p)
# dp[i][j] := True if s[0..i) matches p[0..j)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True

def isMatch(i: int, j: int) -> bool:
return i >= 0 and p[j] == '?' or s[i] == p[j]

for j, c in enumerate(p):
if c == '*':
dp[0][j + 1] = dp[0][j]

for i in range(m):
for j in range(n):
if p[j] == '*':
matchEmpty = dp[i + 1][j]
matchSome = dp[i][j + 1]
dp[i + 1][j + 1] = matchEmpty or matchSome
elif isMatch(i, j):
dp[i + 1][j + 1] = dp[i][j]

return dp[m][n]
``````