力扣 44. 通配符匹配 dp

https://leetcode-cn.com/problems/wildcard-matching/

思路：$dp[i][j]$dp[i][j]表示$a$a的前$i$i个字符和$b$b的前$j$j个字符能否匹配。那么答案就是$dp[n][m]$dp[n][m]，现在考虑怎么转移，因为两个字符串的下标都是从$0$0开始的，所以要通过$i-1、j-1$i−1、j−1的关系来推出$dp[i][j]$dp[i][j]的状态。$(1)$(1)如果$b[j-1]$b[j−1]不等于$*$∗，那么当$a[i-1]=b[j-1]$a[i−1]=b[j−1]或$b[j-1]='？'$b[j−1]=′？′时，有$dp[i][j]=dp[i-1][j-1]$dp[i][j]=dp[i−1][j−1]；$(2)$(2)如果$b[j-1]$b[j−1]等于$*$∗，这时实际上有两种情况，第一种就是$a[i-1]$a[i−1]不和$b[j-1]$b[j−1]匹配，也就是说$a$a的前$i$i个字符和$b$b的前$j-1$j−1个字符匹配，所以有$dp[i][j]=dp[i][j]||dp[i][j-1]$dp[i][j]=dp[i][j]∣∣dp[i][j−1]；当然还有第二种情况，就是$a[i-1]$a[i−1]和$b[j-1]$b[j−1]匹配，那么前一个状态就是$a$a的前$i-1$i−1个字符和$b$b的前$j$j个字符匹配，所以有$dp[i][j]=dp[i][j]||dp[i-1][j]$dp[i][j]=dp[i][j]∣∣dp[i−1][j]。

class Solution {
public:
    bool isMatch(string a, string b) {
        int n=a.size(),m=b.size();
        vector<vector<bool>> dp(n+1);
        for(int i=0;i<=n;i++)
            dp[i].resize(m+1);
        dp[0][0]=1;
        for(int i=1;i<=n;i++)
            dp[i][0]=0;
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
            {
                if(i&&j&&b[j-1]!='*')
                {
                    if(a[i-1]==b[j-1]||b[j-1]=='?')
                        dp[i][j]=dp[i-1][j-1];
                }
                else if(j&&b[j-1]=='*')
                {
                    dp[i][j]=dp[i][j]||dp[i][j-1];//不和*匹配
                    if(i)
                        dp[i][j]=dp[i][j]||dp[i-1][j];
                }
            }
        }
        return dp[n][m];
    }
};