/*
* @lc app=leetcode id=44 lang=cpp
*
* [44] Wildcard Matching
*
* https://leetcode.com/problems/wildcard-matching/description/
*
* algorithms
* Hard (23.27%)
* Likes: 1247
* Dislikes: 78
* Total Accepted: 192.8K
* Total Submissions: 827.3K
* Testcase Example: '"aa"\n"a"'
*
* Given an input string (s) and a pattern (p), implement wildcard pattern
* matching with support for '?' and '*'.
*
*
* '?' Matches any single character.
* '*' Matches any sequence of characters (including the empty sequence).
*
*
* The matching should cover the entire input string (not partial).
*
* Note:
*
*
* s could be empty and contains only lowercase letters a-z.
* p could be empty and contains only lowercase letters a-z, and characters
* like ? or *.
*
*
* 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
*
*
*/
class Solution {
public:
bool isMatch(string s, string p) {
const int M = s.size(), N = p.size();
vector<vector<bool>> dp(M + 1, vector<bool>(N + 1));
dp[0][0] = true;
for (int j = 1; j <= N; ++j) {
if (p[j - 1] == '*') dp[0][j] = dp[0][j - 1];
}
for (int i = 1; i <= M; ++i) {
for (int j = 1; j <= N; ++j) {
const char c = p[j - 1];
if (c == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
} else if (s[i - 1] == c || c == '?') {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[M][N];
}
};