Wildcard Matching

Problem Id: 44 Difficulty: Hard Tag: String Tag: Dynamic Programming Tag: Backtracking Tag: Greedy


Intuition

Dynamic programming.

  1. Using dp[i][j]: Boolean to mark whether s[:i] can match p[:j].
  2. If p[j - 1] == '*', dp[i][j] = dp[i - 1][j] or dp[i][j - 1].
  3. If p[j - 1] == '?', dp[i][j] = dp[i - 1][j - 1].
  4. If p[j - 1] is neither * nor ?, dp[i][j] = dp[i - 1][j - 1] and ``s[i - 1] == p[j - 1].

Solution


class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
        dp[0][0] = True

        for i in range(len(s) + 1):
            for j in range(1, len(p) + 1):
                if p[j - 1] == '*':
                    if i > 0 and dp[i - 1][j]:
                        dp[i][j] = True
                    if dp[i][j - 1]:
                        dp[i][j] = True
                elif p[j - 1] == '?':
                    if i > 0:
                        dp[i][j] = dp[i - 1][j - 1]
                else:
                    if i > 0:
                        dp[i][j] = dp[i - 1][j - 1] and (s[i - 1] == p[j - 1])
        return dp[-1][-1]