> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/dynamic-programming/44-wildcardmatching.md).

# 44     Wildcard Matching

## 44. [Wildcard Matching](https://leetcode.com/problems/wildcard-matching/description/)

## 1. Question

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
```

## 2. Implementation

**(1) Two Pointers**

```java
class Solution {
    public boolean isMatch(String s, String p) {
        int sIndex = 0, pIndex = 0;
        int matchIndex = -1, starIndex = -1;

        while (sIndex < s.length()) {
            // case 1: p.charAt(pIndex) == s.charAt(sIndex) 或者 p.charAt(pIndex) == ?时， pIndex所在的位置匹配sIndex的字符
            // 同时移动pIndex和sIndex
            if (pIndex < p.length() && (p.charAt(pIndex) == s.charAt(sIndex) || p.charAt(pIndex) == '?')) {
                ++pIndex;
                ++sIndex;
            }
            // case 2: 如果p.charAt(pIndex)为*， 此时的*可能不匹配任何s的子串，所以保留starIndex，之后可能会用到，并且我们先不移动sIndex
            // (因为*可能不匹配任何s的子串), 并
            else if (pIndex < p.length() && p.charAt(pIndex) == '*') {
                starIndex = pIndex;
                ++pIndex;
                // 此时的 sIndex 还不确定是否要被 * 表示，需要继续从sIndex开始遍历，如果后面某个位置发生匹配错误，
                // 则表示sIndex应该被*表示，重新回复从 sIndex+1 开始重新匹配
                matchIndex = sIndex;
            }
            // case 3: 匹配失败，说明matchIndex指向的字符应该被*表示，回溯到matchIndex+1，重新开始进行 starIndex+1和matchIndex+1匹配
            else if (starIndex > -1) {
                pIndex = starIndex + 1;
                sIndex = matchIndex + 1;
                ++matchIndex;
            }
            else {
                return false;
            }
        }

        //s已经遍历完，p按理最多只剩下*，如果还存在非*字母，则匹配失败
        while (pIndex < p.length() && p.charAt(pIndex) == '*') {
            ++pIndex;
        }
        return pIndex == p.length();
    }
}
```

**(2) DP**

[解析](http://shmilyaw-hotmail-com.iteye.com/blog/2154716)

```java
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];

        dp[0][0] = true;

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

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
                else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else {
                    dp[i][j] = false;
                }
            }
        }
        return dp[m][n];
    }
}
```

## 3. Time & Space Complexity

**Two Pointers:** 时间复杂度O(mn), 空间复杂度O(1)

**DP**: 时间复杂度O(mn), 空间复杂度O(mn)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://protegejj.gitbook.io/algorithm-practice/leetcode/dynamic-programming/44-wildcardmatching.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.