# 44.Wildcard-Matching

## 44. Wildcard Matching

## 题目地址

<https://leetcode.com/problems/wildcard-matching/>

<https://blog.csdn.net/jmspan/article/details/51460021>

## 题目描述

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

## 代码

### Approach 1: DFS

```java
class Solution {
  public boolean isMatch(String s, String p) {
        if (s == null || p == null) return false;
    if (s.length() == 0 || p.length() == 0)    return false;

    return dfs(s, 0, p, 0);
  }

  private boolean dfs(String s, int sIdx, String p, int pIdx) {
    if (sIdx == s.length() || pIdx == p.length()) {
      if (sIdx == s.length() && pIdx == p.length()) {
        return true;
      } else {
        return false;
      }
    }

    if (p.charAt(pIdx) == '*') {
      // remove continuous *
      while (p.charAt(pIdx) == '*')
          pIdx++;
        if (pIdx == p.length())    return true;
      }

            // compare remaining part of p after * with s
      while (sIdx < s.length() && !dfs(s, sIdx, p, pIdx)) {
        sIdx++;
      }

      // sIdx 不能为空
      return sIdx != s.length();
    } else if (s.charAt(sIdx) == p.chaAt(pIdx) || p.charAt(pIdx) == '?') {
      return dfs(s, sIdx + 1, p, pIdx + 1);
    } else {
      return false;
    }
    }
}
```

### Approach #2 Dynamic Programming

Time complexity : O(*SP*) && Space complexity : O(*SP*) to keep the matrix.

```java
class Solution {
  public boolean isMatch(String s, String p) {
    int sLen = s.length(), pLen = p.length();

    // base cases
    if (p.equals(s) || p.equals("*")) return true;
    if (p.isEmpty() || s.isEmpty()) return false;

    // init all matrix except [0][0] element as False
    boolean[][] d = new boolean[pLen + 1][sLen + 1];
    d[0][0] = true;

    // DP compute
    for (int pIdx = 1; pIdx < pLen + 1; pIdx++) {
      // the current character in the pattern is '*'
      if (p.charAt(pIdx - 1) == '*') {
        int sIdx = 1;
        // d[p_idx - 1][s_idx - 1] is a string-pattern match
        // on the previous step, i.e. one character before.
        // Find the first idx in string with the previous math.
        while ((!d[pIdx - 1][sIdx - 1]) && (sIdx < sLen + 1))     sIdx++;
        // If (string) matches (pattern),
        // when (string) matches (pattern)* as well
        d[pIdx][sIdx - 1] = d[pIdx - 1][sIdx - 1];
        // If (string) matches (pattern),
        // when (string)(whatever_characters) matches (pattern)* as well
        while (sIdx < sLen + 1)     d[pIdx][sIdx++] = true;
      }
      // the current character in the pattern is '?'
      else if (p.charAt(pIdx - 1) == '?') {
        for (int sIdx = 1; sIdx < sLen + 1; sIdx++)
          d[pIdx][sIdx] = d[pIdx - 1][sIdx - 1];
      }
      // the current character in the pattern is not '*' or '?'
      else {
        for (int sIdx = 1; sIdx < sLen + 1; sIdx++) {
          // Match is possible if there is a previous match
          // and current characters are the same
          d[pIdx][sIdx] = d[pIdx - 1][sIdx - 1] &&
                  (p.charAt(pIdx - 1) == s.charAt(sIdx - 1));
        }
      }
    }
    return d[pLen][sLen];
  }
}
```

### Approach #3 Dynamic Programming - 2

```java
boolean strmatch(String str, String pattern, int n, int m) { 
        // empty pattern can only match with 
        // empty string 
        if (m == 0) 
            return (n == 0); 

        // lookup table for storing results of 
        // subproblems 
        boolean[][] lookup = new boolean[n + 1][m + 1]; 

        // initailze lookup table to false 
        for(int i = 0; i < n + 1; i++) 
            Arrays.fill(lookup[i], false); 


        // empty pattern can match with empty string 
        lookup[0][0] = true; 

        // Only '*' can match with empty string 
        for (int j = 1; j <= m; j++) 
            if (pattern.charAt(j - 1) == '*') 
                lookup[0][j] = lookup[0][j - 1]; 

        // fill the table in bottom-up fashion 
        for (int i = 1; i <= n; i++) 
        { 
            for (int j = 1; j <= m; j++) 
            { 
                // Two cases if we see a '*' 
                // a) We ignore '*'' character and move 
                //    to next  character in the pattern, 
                //     i.e., '*' indicates an empty sequence. 
                // b) '*' character matches with ith 
                //     character in input 
                if (pattern.charAt(j - 1) == '*') 
                    lookup[i][j] = lookup[i][j - 1] || 
                                   lookup[i - 1][j]; 

                // Current characters are considered as 
                // matching in two cases 
                // (a) current character of pattern is '?' 
                // (b) characters actually match 
                else if (pattern.charAt(j - 1) == '?' || 
                    str.charAt(i - 1) == pattern.charAt(j - 1)) 
                    lookup[i][j] = lookup[i - 1][j - 1]; 

                // If characters don't match 
                else lookup[i][j] = false; 
            } 
        } 

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

### Approach #3 Backtracking

Time complexity : O(min(*S*,*P*)) && Space complexity : O(1)

```java
class Solution {
  public boolean isMatch(String s, String p) {
    int sLen = s.length(), pLen = p.length();

    int sIdx = 0, pIdx = 0;
    int starIdx = -1, sTmpIdx = -1;
    while (sIdx < sLen) {
      // If the pattern caracter = string character
      // or pattern character = '?'
      if (pIdx < pLen && (p.charAt(pIdx) == '?' || p.charAt(pIdx) == s.charAt(sIdx))){
        ++sIdx;
        ++pIdx;
      }
      // If pattern character = '*'
      else if (pIdx < pLen && p.charAt(pIdx) == '*') {
        // Check the situation
        // when '*' matches no characters
        starIdx = pIdx;
        sTmpIdx = sIdx;
        ++pIdx;
      }
      // If pattern character != string character
      // or pattern is used up
      // and there was no '*' character in pattern 
      else if (starIdx == -1) {
        return false;
      }
      // If pattern character != string character
      // or pattern is used up
      // and there was '*' character in pattern before
      else {
        // Backtrack: check the situation
        // when '*' matches one more character
        pIdx = starIdx + 1;
        sIdx = sTmpIdx + 1;
        sTmpIdx = sIdx;
      }
    }

    // The remaining characters in the pattern should all be '*' characters
    for (int i = pIdx; i < pLen; i++)
      if (p.charAt(i) != '*') return false;
    return true;
  }
}
```


---

# 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://wentao-shao.gitbook.io/leetcode/graph-search/44.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.