44. Wildcard Matching

Posted on Edited on In

44. Wildcard Matching

Description

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

  • '?' Matches any single character.
  • '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Example 1:

1
2
3
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

1
2
3
Input: s = "aa", p = "*"
Output: true
Explanation:'*' matches any sequence.

Example 3:

1
2
3
Input: s = "cb", p = "?a"
Output: false
Explanation:'?' matches 'c', but the second letter is 'a', which does not match 'b'.

Constraints:

  • 0 <= s.length, p.length <= 2000
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '?' or '*'.

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    int n1, n2;
    vector<vector<int>> dp;

    bool isMatch(string s, string p) {
        n1 = s.size();
        n2 = p.size();
        dp.resize(n1, vector<int>(n2, -1));
        return dfs(0, 0, s, p);
    }

    bool dfs(int idx1, int idx2, string& s, string& p) {
        if (idx1 == n1) {
            if (idx2 == n2) {
                return true;
            } else if (p[idx2] == '*') {
                return dfs(idx1, idx2 + 1, s, p);
            } else {
                return false;
            }
        }
        if (idx2 == n2) {
            return false;
        }
        if (dp[idx1][idx2] != -1) {
            return dp[idx1][idx2];
        }
        int& res = dp[idx1][idx2];
        if (s[idx1] == p[idx2] || p[idx2] == '?') {
            res = dfs(idx1 + 1, idx2 + 1, s, p);
            return res;
        } else if (p[idx2] == '*') {
            for (int idx = idx1; idx <= n1; idx++) {
                res = dfs(idx, idx2 + 1, s, p);
                if (res) {
                    return res;
                }
            }
        }
        res = false;
        return res;
    }
};