44. Wildcard Matching

Problem Statement in English

You’re given an input string s and a pattern p, implement wildcard pattern matching with support for '?' and '*'.

Approach

I will present three different approaches to solve the problem, each more efficient than the last.

The first two rely on dynamic programming, while the third approach uses a greedy algorithm.

The reason dynamic programming works here is because the solution to the current index depends on whether the subsequent substrings match, which can be computed recursively. And cached.

Top-Down Dynamic Programming

The first approach uses a top-down dynamic programming method, which is straightforward, but can lead to time limit exceeded (TLE) errors for larger inputs.

So, when we’re comparing index i of the input string and index j of the pattern, we can recursively check if the substrings starting from these indices match. If they do, we return True, otherwise we return False.

When we encounter a *, we have two choices: either we can match it with the current character in the input string and move to the next character in the input string, or we can skip the * and move to the next character in the pattern.

Also remember that if we reach the end of the input string, the remaining characters in the pattern must all be * for a match to occur.

Bottom-Up Dynamic Programming

The second approach employs a bottom-up dynamic programming technique, which is more efficient and avoids TLE-ing. Our bottom-up approach uses a 1D array to store the results of previous computations, and another array for the current computations, allowing us to build the solution iteratively.

This method reduces space complexity compared to a full 2D DP table. Let’s say the length of the input string is N1 and the length of the pattern is N2.

Here the row index represents the substring of the input string, while the column index represents the substring of the pattern. So the last row of the DP table will represent the input string after the N1th character (essentially an empty string), and the last column will represent the pattern after the N2th character (also an empty string).

Thus, we will compute N1 + 1 rows (because when we’re computing the result for the N1 - 1th index in the first iteration, we’ve already got the row at index N1 in the dp list) and N2 + 1 columns.

N2 + 1 columns because that’s the size of the arrays we allocate, since dp[i][N2] (bear in mind that i is the iteration since we’re not actually maintaining a 2D array), where 0 <= i < N1 represents whether s[i:] matches p[N2:] which is always False since a non-empty string cannot match an empty pattern. The last column is always False except for the last row (i = N1), which is True because an empty string matches an empty pattern.

The value at dp[i][j] will be True if the substring of the input string starting from index i matches the substring of the pattern starting from index j, and False otherwise.

The way we handle the * and ? characters is similar to the top-down approach.

If we encounter a *, we can either match it with the current character in the input string and move to the next character in the input string, or we can skip the * and move to the next character in the pattern. So in terms of the DP table, dp[i][j] will be True if either dp[i + 1][j] (matching the * with the current character) or dp[i][j + 1] (skipping the *) is True.

If we encounter a ?, we can match it with the current character in the input string and move to the next character in the input string. And here dp[i][j] will be True if dp[i + 1][j + 1] is True.

Greedy Algorithm

Finally, the third approach utilizes a greedy algorithm that achieves optimal space complexity. The greedy approach operates on the fact that a * can match any sequence of characters, including an empty sequence. The algorithm maintains two pointers: one for the input string and one for the pattern. It also keeps track of the last position of a * in the pattern and the corresponding position in the input string.

When a mismatch occurs, the algorithm backtracks to the last * and tries to match more characters from the input string with it. It essentially tries to “expand” the match for the *, one character at a time until a match is found, or all possibilities are exhausted.

This approach is efficient and works well for large inputs.

Solution in Python

Dynamic Programming, Top-Down (TLE):


class Solution:
  def isMatch(self, s: str, p: str) -> bool:
    N1, N2 = len(s), len(p)

    @cache
    def dp(i, j):
      if j == N2:
        return i == N1

      # If string is fully consumed, remaining pattern must all be '*'
      if i == N1:
        return p[j] == "*" and dp(i, j + 1)

      # Match logic
      if p[j] == "*":
        return dp(i + 1, j) or dp(i, j + 1)

      if p[j] == "?" or s[i] == p[j]:
        return dp(i + 1, j + 1)

      return False

    return dp(0, 0)

Dynamic Programming, Bottom-Up: $O(N1 * N2)$


class Solution:

  def isMatch(self, s: str, p: str) -> bool:
    N1, N2 = len(s), len(p)

    # dp[j] represents whether s[i:] matches p[j:]
    # Initialize for base case i == N1 (empty string s)
    dp = [False] * (N2 + 1)
    dp[N2] = True

    # Base case setup: p matching empty s
    for j in reversed(range(N2)):
      if p[j] == "*":
        dp[j] = dp[j + 1]

    # Fill table bottom-up from i = N1-1 down to 0
    for i in reversed(range(N1)):
      new_dp = [False] * (N2 + 1)

      for j in reversed(range(N2)):
        if p[j] == "*":
          # dp[j] is matching s[i+1:], new_dp[j+1] is skipping *
          new_dp[j] = dp[j] or new_dp[j + 1]
        elif p[j] == "?" or s[i] == p[j]:
          # Diagonal move: depends on s[i+1:] and p[j+1:]
          new_dp[j] = dp[j + 1]

      dp = new_dp

    return dp[0]

Optimal Space Solution (Greedy): $O(1)$


class Solution:
  def isMatch(self, s: str, p: str) -> bool:
    s_idx = p_idx = 0
    star_idx = s_tmp_mark = -1

    while s_idx < len(s):
      # Case 1: Match single character or '?'
      if p_idx < len(p) and (p[p_idx] == "?" or p[p_idx] == s[s_idx]):
        s_idx += 1
        p_idx += 1
      # Case 2: Found '*', record checkpoint
      elif p_idx < len(p) and p[p_idx] == "*":
        star_idx = p_idx
        s_tmp_mark = s_idx
        p_idx += 1
      # Case 3: Mismatch, backtrack to last '*'
      elif star_idx != -1:
        p_idx = star_idx + 1
        s_tmp_mark += 1
        s_idx = s_tmp_mark
      # Case 4: Mismatch and no '*' to backtrack to
      else:
        return False

    # Check remaining pattern for trailing '*'
    return all(x == "*" for x in p[p_idx:])

Mistakes I Made

I had to look this up :(

And we are done.

Problem Statement in English#

Approach#

Top-Down Dynamic Programming#

Bottom-Up Dynamic Programming#

Greedy Algorithm#

Solution in Python#

Mistakes I Made#