動機

很有趣的dp

Problem

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 = aOutput: falseExplanation: a does not match the entire string aa.

Example 2:

Input: s = aa, p = *Output: trueExplanation: '*' matches any sequence.

Example 3:

Input: s = cb, p = ?aOutput: falseExplanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input: s = adceb, p = *a*bOutput: trueExplanation: The first '*' matches the empty sequence, while the second '*' matches the substring dce.

Example 5:

Input: s = acdcb, p = a*c?bOutput: false

 

Constraints:

  • 0 <= s.length, p.length <= 2000
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '?' or '*'.

Sol

原本在i < 0的case想說讓遞迴處理*，但是這樣會讓後面的i都要重新檢查，同時會因為*的case導致最後不論如何都會變成true或是loop 所以直接處理掉了

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @cache
        def dp(i,j):
            if i < 0 and j < 0:
                return True
            elif j < 0:
                return False
            elif i < 0:
                return all([c == '*' for c in p[:j+1]])
                # return dp(i,j-1)
            elif p[j] == '?':
                return dp(i-1,j-1)
            elif p[j] == '*':
                # single, none
                return dp(i-1,j) or dp(i,j-1)
            else:
                if s[i] == p[j]:
                    return dp(i-1,j-1)
                else:
                    return False
        return dp(len(s)-1,len(p)-1)