Problem statement

https://leetcode.com/problems/wildcard-matching/

Solution

Another classical DP problem, similar to problem 0010. Let us define by dp(i, j) answer to the question if s[:i+1] and p[:j+1] can be matched. Then we can have different cases:

  1. if i == -1 and j == -1 it means, that we reached both empty strings, we return True.
  2. if i == -1, it means, that s string is empty (and t is not empty), in this case we are happy only if all symbols of p are equal to *, so we check last symbol check dp(i, j-1).
  3. if j == -1, but i is not equal to -1, we already checked it previously, we return False.
  4. if s[i] == p[j], that is last symbols are equal, we remove them and go to dp(i-1, j-1)
  5. if p[j] not equal to ? or * (that is it is letter) and it is not equal to s[i], we can not match, so we return False.
  6. if p[j] is equal to ?, we can match in only one way and we again go to dp(i-1, j-1).
  7. finally, if we have * as p[j], we can have two options: we either say that this * is finished already, so we delete it, or not finished yet, then we delete symbol from s.

Complexity

Complexity: time and space complexity is O(mn).

Code

class Solution:
    def isMatch(self, s, p):
        @lru_cache(None)
        def dp(i, j):
            if i == -1 and j == -1: return True
            if i == -1: return dp(i, j-1) and p[j] == "*"
            if j == -1: return False

            if s[i] == p[j]: return dp(i-1, j-1)
            if s[i] != p[j] and p[j] not in "?*": return False
            if p[j] == "?": return dp(i-1, j-1)
            if p[j] == "*": return dp(i-1, j) or dp(i, j-1)
            
        return dp(len(s) - 1, len(p) - 1)