Home Wildcard Matching
Post
Cancel

LeetCode #44: Wildcard Matching (C/C++).

hard

source: https://leetcode.com/problems/wildcard-matching/
C/C++ Solution to LeetCode problem 44. Wildcard Matching.

Problem


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

Examples


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’.

Constraints


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

Solution


This problem can be solved with Dynamic Programming:

  • First we clean the pattern string (remove the extra consecutive '*').
  • We use two indexes to track what character of the pattern and string we are matching.
  • If the indexes are at the end of the pattern and string, then we found a match.
  • If only the index of pattern is at the end, there was no match.
  • If the pattern at the current index has '*' we have three options:
    • Move index of pattern.
    • Move index of string.
    • Move both indexes.
  • Else if the char at the pattern and string are equal, or the pattern has a ?, then we can move to next position in both indexes.
  • Else, there is no match.

Solution


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
45
46
47
48
49
50
class Solution {
private:
  string s;
  string p;
  vector<vector<int>> dp;

  void cleanPattern() {
    int l=0;

    for (int i=0; i<p.size(); i++) {
      if (i>0 && p[i] == p[i-1] && p[i] == '*')
        continue;
      
      if (l != i)
        p[l] = p[i];
      l++;
    }
    p.resize(l);
  }

public:
  bool compare(int i, int j) {
    if (dp[i][j] != -1)
      return dp[i][j];

    if (i>=s.size() && j>=p.size())
      return true;
    if (j>=p.size())
      return false;

    bool m = i<s.size() && (s[i] == p[j] || p[j] == '?');
    if (p[j] == '*')
      dp[i][j] = compare(i, j+1) || (i<s.size() && (compare(i+1, j+1) || compare(i+1, j)));
    else if (m)
      dp[i][j] = compare(i+1, j+1);
    else
      dp[i][j] = false;
      
    return dp[i][j];
  }

  bool isMatch(string s, string p) {
    this->s = s;
    this->p = p;

    cleanPattern();
    dp = vector(this->s.size() + 1, vector(this->p.size() + 1, -1));
    return compare(0, 0);
  }
};
This post is licensed under CC BY 4.0 by the author.

Binary Tree Inorder Traversal

Permutation Sequence