> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/string-match/wildcard-matching.md).

# Wildcard Matching

> 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).
>
> The function prototype should be:
>
> bool isMatch(const char \*s, const char \*p)
>
> Some examples:
>
> isMatch("aa","a") → false
>
> isMatch("aa","aa") → true
>
> isMatch("aaa","aa") → false
>
> isMatch("aa", "\*") → true
>
> isMatch("aa", "a\*") → true
>
> isMatch("ab", "?\*") → true
>
> isMatch("aab", "c\*a\*b") → false

## Thoughts

问s是否match p, p中?代表任意一个字符, \*代表任意字符重复任意次。字符串匹配问题首先想到DP。相等或'?'时没什么特别的。星号表示任意的字符可以出现0个或以上, 0个时即dp\[i]\[j-1]；0个以上时即（再）用star match了s\[i]字符，star已经match了i-1，即dp\[i-1]\[j]。

## Code

```cpp
/*
 * @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];
    }
};


```

## Analysis

时间复杂度O(MN).