1、前言

2、思路

这道题与第10题的正则表达式匹配一毛一样，甚至连解法都差不多。都是先匹配第一个，如果遇到特殊匹配符号，然后接着选或者不选。

3、代码

class Solution {
    public boolean isMatch(String s, String p) {
        if(s == null || p == null){
            return false;
        }

        Boolean[][] memo = new Boolean[s.length()][p.length()];

        return dfs(s, 0, p, 0, memo);
    }

    private boolean dfs(String s, int i, String p, int j, Boolean[][] memo){
        if(j == p.length()){
            return i == s.length();
        }

        if(i < s.length() && j < p.length() && memo[i][j] != null){
            return memo[i][j];
        }

        boolean firstMatch = i < s.length() && j < p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?' || p.charAt(j) == '*');

        boolean res = false;
        if(p.charAt(j) == '*'){
            res = dfs(s, i, p, j + 1, memo) || (firstMatch && dfs(s, i + 1, p, j, memo));
        }else{
            res = firstMatch && dfs(s, i + 1, p, j + 1, memo);
        }

        if(i < s.length() && j < p.length()){
            memo[i][j] = res;
        }
        
        return res;
    }
}