题解 | #通配符匹配#

解题思路：=======>动态规划

1、定义状态：f[i][j]表示字符串s中以i结尾的子串和字符串p中以j结尾的子串是否匹配。

2、状态转移：

如果p[j]=='?'则需要f[i-1][j-1]&&s[i]为任意字符即可

如果p[j]=='字符，则需要f[i-1][j-1]&&s[i]==p[j]

如果p[j]=='*',则f[i][j]=f[i][j-1]||f[i-1][j-1]||f[i-2][j-1].....||f[i-k][j-1] f[i-1][j]=f[i-1][j-1]||f[i-2][j-1]||f[i-3][j-1]....||f[i-k-1][j-1] ===》优化：f[i][j]=f[i-1][j]||f[i][j-1];

public class Solution {
    public boolean isMatch(String s, String p) {
        int n=s.length();
        int m=p.length();
        String ss=" "+s;
        String pp=" "+p;
        char[]S=ss.toCharArray();
        char[]P=pp.toCharArray();
        boolean[][]f=new boolean[n+1][m+1];//定义状态
        f[0][0]=true;//初始f[0][0]
        for(int i=0;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(P[j]=='*'){
                    f[i][j]=(i-1>=0&&f[i-1][j])||f[i][j-1];
                }
                else{
                    f[i][j]=(i-1>=0&&f[i-1][j-1])&&(P[j]==S[i] || P[j]=='?' );
                }
            }
        }
        return f[n][m];
    }
}