1、前言

2、思路

这道题的思路就是使用 dfs，首先匹配第一个字符串，包括 "." 的情况。

然后看后面的字符串是否为 "*"，如果是，则有匹配0和多个的情况：

• 匹配0个，则 i 不变， j + 2
• 匹配多个，则 i + 1，j 不变，并且要与上第一次匹配的情况
  如果不是，则第一次匹配的情况与上 i + 1 和 j + 1

3、代码

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

    private boolean dfs(String s, int i, String p, int j){
        if(j == p.length()){
            return i == s.length();
        }
        
        boolean firstMatch = i < s.length() && j < p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
        boolean ans = false;
        if(j + 1 < p.length() && p.charAt(j + 1) == '*'){
            ans = dfs(s, i, p, j + 2) || (firstMatch && dfs(s, i + 1, p, j));
        }else{
            ans = firstMatch && dfs(s, i + 1, p, j + 1);
        }

        return ans;
    }
}