Skip to main content

Wildcard Matching (LeetCode Problem - solution)

Problem Statement​

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≤20000 \leq \text{s.length}, \text{p.length} \leq 2000
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '?' or '*'.
  • It is guaranteed for each appearance of the character '*' there will be a previous valid character to match.

Solution​

The problem can be solved using dynamic programming. We can create a 2D array dp of size n+1 x m+1 where n is the length of the string s and m is the length of the pattern p. The value of dp[i][j] will be true if the first i characters of the string s match the first j characters of the pattern p.

The base case will be dp[0][0] = true as an empty string matches an empty pattern. The value of dp[i][0] will be false as an empty pattern cannot match a non-empty string. The value of dp[0][j] will be true if the pattern p consists of only * characters.

For each cell dp[i][j], we will check the following conditions:

  1. If the ithi^{th} character of the string s matches the jthj^{th} character of the pattern p or the jthj^{th} character of the pattern p is ?, then dp[i][j] = dp[i-1][j-1].
  2. If the jthj^{th} character of the pattern p is *, then dp[i][j] = dp[i-1][j] || dp[i][j-1].

Finally, the value of dp[n][m] will be the answer.

Written by @ajay-dhangar
 /**
* @param {string} s
* @param {string} p
* @return {boolean}
*/

var isMatch = function(s, p) {
let n = s.length;
let m = p.length;
let dp = new Array(n+1).fill(false).map(() => new Array(m+1).fill(false));
dp[0][0] = true;

for (let j = 1; j <= m; j++) {
if (p[j-1] === '*') {
dp[0][j] = dp[0][j-1];
}
}

for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
if (s[i-1] === p[j-1] || p[j-1] === '?') {
dp[i][j] = dp[i-1][j-1];
} else if (p[j-1] === '*') {
dp[i][j] = dp[i-1][j] || dp[i][j-1];
}
}
}

return dp[n][m];
};

Complexity Analysis​

The time complexity for the above approach is O(n×m)O(n \times m) where n is the length of the string s and m is the length of the pattern p.

The space complexity is O(n×m)O(n \times m) as we are using a 2D array of size n+1 x m+1.

Video Content For Better Understanding​

References​


Authors:

Loading...
Loading...