leetcode题解44：通配符匹配

描述

该题来自于力扣第44题

分析

类似于leetcode题解10，同样使用动态规划来解，定义dp[i][j]为字符串s的前i位与字符串p的前j为匹配的结果，则dp[0][0]表示两个空串的比较，自然为True；对于i>=1和j>=1不难知道状态转移方程为
\[ dp[i][j] = \left\{ \begin{aligned} & dp[i-1][j-1] & p[j-1]=? \\ & dp[i-1][j] \quad \text{or} \quad dp[i][j-1] & p[j-1]=* \\ & dp[i-1][j-1] \quad \text{and} \quad s[i-1][j-1] & \text{others} \end{aligned} \right. \]

最后注意边界，主要是dp[0][j]这种情况。

代码

python

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

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