44. 通配符匹配

44. 通配符匹配

方法一：
动态规划

动态规划：dp[i][j]表示：s的前i个字符与p的前j个字符是否匹配
状态转移方程

如果s1的第 i 个字符和s2的第 j 个字符相同，或者s2的第 j 个字符为 “?”
f[i][j] = f[i - 1][j - 1]
如果s2的第 j 个字符为 *
若s2的第 j 个字符匹配空串, f[i][j] = f[i][j - 1]
若s2的第 j 个字符匹配s1的第 i 个字符, f[i][j] = f[i - 1][j]

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

        dp = [ [False]*(plen+1) for _ in range(slen+1)]
        # 先将dp数组的第0行和第0列初始化
        # 下面是初始化dp[i][0]显然都是False，所以不用初始化
        # dp[0][0]显然是True
        dp[0][0] = True
        # 下面是初始化dp[0][j]
        for j in range(1,plen+1):
            dp[0][j] = dp[0][j-1] and p[j-1]=='*'

        for i in range(1,slen+1):
            for j in range(1,plen+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[slen][plen]

方法二：回溯
我实在没看懂