leetcode题解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

```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)]