# 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).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/string-match/wildcard-matching.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.