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); } };