[LeetCode] 44. Wildcard Matching

Table of Contents

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:

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 \leq 2000$
• s contains only lowercase English letters.
• p contains only lowercase English letters, '?', or '*'.

Approach

We use a dynamic programming approach. The method builds a dynamic table tracking substring matches between an input string and pattern, efficiently handling wildcard characters ? and * by exploring all possible matching scenarios through strategic table population.

Solution

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
  // Convert strings to arrays with an empty string at the start for easier 1-based indexing
  const strArr = ["", ...s];
  const patternArr = ["", ...p];

  // dp[i][j] indicates whether patternArr[1..i] matches strArr[1..j]
  const dp = new Array(patternArr.length)
    .fill(null)
    .map(() => new Array(strArr.length).fill(false));

  // Base case: empty pattern matches empty string
  dp[0][0] = true;

  // Empty pattern cannot match any non-empty string
  for (let j = 1; j < strArr.length; j++) {
    dp[0][j] = false;
  }

  // Empty string can match pattern prefixes consisting only of '*'
  for (let i = 1; i < patternArr.length; i++) {
    dp[i][0] = patternArr[i] === "*" && dp[i - 1][0];
  }

  // Fill the DP table
  for (let i = 1; i < patternArr.length; i++) {
    const isStar = patternArr[i] === "*";
    const isQuestionMark = patternArr[i] === "?";

    for (let j = 1; j < strArr.length; j++) {
      if (isStar) {
        // '*' can match:
        // 1. empty sequence (ignore '*'): dp[i - 1][j]
        // 2. extend previous match with one more character: dp[i][j - 1]
        // 3. single character match: dp[i - 1][j - 1]
        dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i - 1][j - 1];
      } else if (isQuestionMark) {
        // '?' matches exactly one character, so check previous substrings
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        // Exact character match and previous substrings matched
        dp[i][j] = dp[i - 1][j - 1] && patternArr[i] === strArr[j];
      }
    }
  }

  // Return whether the entire pattern matches the entire string
  return dp[patternArr.length - 1][strArr.length - 1];
};

Complexity Analysis

Time Complexity

The time complexity is $O(m \times n)$, where $m$ is the length of the string s and $n$ is the length of the pattern p. This is because we fill DP table of size $(m+1) \times (n+1)$.

Space Complexity

The space complexity is $O(m \times n)$ due to the DP table.