今天是紀錄LeetCode解題的第四十四天
是一題困難題

第四十四題題目：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).

給定一個字串s和欲匹配字符p，實作字符匹配，其中' ? '匹配任意單一字元，' * '匹配任意字元序列(包括空序列)，匹配範圍應覆蓋整個輸入字串（不能部分匹配）

解題思路

不知道大家還記不記得day10_Regular Expression Matching，這兩題非常類似，只是要處理的' ? '和' * '規則不一樣，這題一樣用動態規劃解題，如果不熟悉的可以去看day10的文章，有比較簡單的動態規劃題目講解

1. 首先，和第十題一樣我們要先定義dp[i][j] = s[：i] 是否能匹配p[：j]（表示s的前i個字母是否能和p的前j個字母匹配）
2. 規則一：p[j-1] == s[i-1] → dp[i][j] = dp[i-1][j-1]，當前字元匹配時，當前狀態取決於前一狀態是否匹配
3. 規則二：p[j-1] == '?' → dp[i][j] = dp[i-1][j-1]，' ? '可以匹配任意字元，所以遇到' ? '把它當作規則一
4. 規則三：p[j-1] == '*' → dp[i][j] = dp[i][j-1] or dp[i-1][j]，' * '可以當作空字串對應狀態轉移為dp[i][j-1]，也可以把它對應字串狀態轉移為dp[i-1][j]

這題的dp表規則推論比較簡單，大家可以試著自己完成填寫這題的dp表格，就會發現上述規則是怎麼來的

程式碼

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

        for j in range(1,n+1):
            if p[j-1] == "*":
                dp[0][j] = dp[0][j-1]
                
        for i in range(1,m+1):
            for j in range(1,n+1):
                if s[i-1] == p[j-1] or p[j-1] == "?":
                    dp[i][j] = dp[i-1][j-1]
                elif p[j-1] == "*":
                    dp[i][j] = dp[i][j-1] or dp[i-1][j]
        return dp[m][n]

DP表格(s="abcdefg" 和 p="a*fg")

• 我們來看這個dp表格，一樣dp[0][0]初始化為True，接著我們看i=1那列(表示s = 'a'去和p匹配)，當i=1、j=1時，s='a'、p='a'這時候匹配成功，dp[1][1] = True，接著看i=1、j=2，這時s='a'、p='a*'，因為' * '可以匹配空字串，所以我們可以直接看左邊那格(i=1、j=1)的狀態是否匹配，由此可知dp[i][j] = dp[i][j-1]，這就是' * '被當空字串時的狀態轉移推論由來

• 再來看i = 2 ~ 7、j = 2時(s = 'ab'、'abc'...、p = 'a*')，這個時候' * '對應的是字串('b'、'bc'...)，我們就看他的上一格狀態(假設s='ab'、p='a*'時，等價於把s當作'a'來看所以我們可以直接看上一格的'a'是否匹配，同理s='abc'時，就把s當作'ab'，那我們就看'ab'是否可以匹配，又可知'ab'是看上一格的狀態得到的，依此類推)，因此我們又推論出dp[i][j] = dp[i-1][j]

• 按照上方dp表格可知這兩個狀態轉移公式只要有一個為True，dp[i][j]就為True，所以整合成dp[i][j] = dp[i][j-1] or dp[i-1][j]