1、前言

2、思路

凡是关于字符串的题，都应该想到指针，那么就应该想到递归（动态规划的转移方程不一定能第一时间想出来，所以能写递归先写递归）。

这道题准备两个指针 i、j，分别为字符串 s、p 的索引，索引从0开始。我们需要对 “.” 和 “” 进行特殊处理。针对 “.”，我们任意的字符都可以匹配；针对 “”，我们可以匹配0个或多个相同的字符。

首先，我们从起始位置开始，先针对性的匹配第一个字符，或者“.”。然后在针对性的匹配字符 “”，匹配字符 “”时要注意首先该字符第二个字符为 “*” 才能进入条件，然后针对这种行为可以忽略此字符，从 j + 2 开始；或者刚才的匹配 && i + 1 跟 j 匹配。

如果不能进入此条件，那么就是刚才的匹配 && 两个索引都往下一个。

3、代码

public class Q10_IsMatch {

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

        return dp(s, 0, p, 0);
    }

    private boolean dp(String s, int i, String p, int j){
        if(j == p.length()){
            return i == s.length();
        }

        boolean firstMath = i < s.length() && j < p.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
        boolean ans = false;
        if(j <= p.length() - 2 && p.charAt(j + 1) == '*'){
            ans =  dp(s, i, p, j + 2) || (firstMath && dp(s, i + 1, p, j));
        }else{
            ans =  firstMath && dp(s, i + 1, p, j + 1);
        }

        return ans;
    }


    public static void main(String[] args) {
        String s = "a", p = "aa";

        System.out.println(new Q10_IsMatch().isMatch(s, p));
    }
}