觉得这篇题解妙的话就来发三连吧(点赞、收藏、加关注hh)👍

Java$(dp)$

时间复杂度：$O(nm)$

思路：

这道题用dp解的话，首先根据闫式dp分析法明确状态表示和状态转移。

状态表示：$f[x][y]$表示$p$从$y$开始到结尾是否能匹配$s$从$x$开始到结尾。(这个状态转移是很容易想到的)

状态转移：
1.如果当前的$p[y]$是字母且与$s[x]$相等，那么$f[x + 1][y + 1]$是否匹配就依赖于$f[x][y]$
2.如果当前的$p[y]$ 是.的话那么也与$s[x]$相等(因为.匹配任何英文字符)，$f[x + 1][y + 1]$是否匹配就依赖于 $f[x][y]$

上述两种情况相似，所以可以合并判断，重点是*这种情况。

3.当前的$p[y]$是*则表示$s[x]$的重复0次还是重复多次分为两种情况：
3.1 如果是重复0次 那么当前的$p[y] == $ *和 $p[y-1]$ 都可以忽略不计(即如果是aa*的话，后面的a*就可以忽略)， 则$f[x][y] = f[x][y+2]$
3.2 如果是重复多次 那么当前的$p[y - 1] == s[x]$ 或者$p[y - 1]== $.，则$f[x][y] = f[x+1][y]$。
(即无论$x$后面有多少个相同字符，都匹配$p[y] == $ *)

最后提交好几次代码，发现了可以提升Java效率的操作:

1. 不管条件语句在哪，每个语句都给个小括号。
2. 即使代码块中语句只有1行，也要加上花括号。

改善Java操作字符串中字符的操作：

将字符串转成字符数组s.toCharArray()，这样就可以直接使用[]而不用s.charAt()那样麻烦了。

class Solution {

    private static int[][] f;
    private static int n;
    private static int m;
    private static char[] s;
    private static char[] p;    

    public boolean isMatch(String s, String p) {
        this.n = s.length();
        this.m = p.length();        
        this.s = s.toCharArray();
        this.p = p.toCharArray();
        f = new int[n + 1][m + 1];
        for(int i = 0; i < n + 1; ++i) {
            Arrays.fill(f[i], - 1);
        }
        return dp(0, 0);
    }

    public static boolean dp(int x, int y) {
        if(f[x][y] != -1) {
            return f[x][y] == 1;
        }

        if(y == m) {
            f[x][y] = (x == n ? 1 : 0);
            return (x == n);
        }
        boolean first = (x < n && (s[x] == p[y] || p[y] == '.'));   
        boolean ans;
        if(y + 1 < m && p[y + 1] == '*') {
            ans = (dp(x, y + 2) || first && dp(x + 1, y));  // 状态转移3
        } else {
            ans = (first && dp(x + 1, y + 1));              // 状态转移1、2
        }

        f[x][y] = ans ? 1 : 0;
        return ans;
    }
}

debug心路历程：耗时$4h$

首先，这道题根本不会，所以就边听课边写代码了。然后将yxc的C++代码改成Java代码，寻思没啥毛病，然后点调试样例试试，结果错了。

然后一遍一遍的对照yxc的代码检查，开始是将f[x][y] > 0来表示f[x][y]等于1或0的布尔结果，接着怀疑Arrays.fill有问题，但是检查发现数组里面的值都正确初始化成$-1$，最后还是改成循环初始化，还是错。然后采用print大法和C++的输出结果进行比对，发现输出的一部分是符合正解的输出结果而且代码流程是一样的。但是突然有一个f[x][y] == 0，可是正解那还是f[x][y] == -1，这就百思不得其解了。

遂将代码重写，发现结果还是错。然后把字符串全局变量改成字符数组全局变量，然后替换所有charAt()为[]来直接访问字符，还是错。然后就检查全局变量中两个字符串的长度n和m有没有赋值到，怀疑到了有没有在类静态变量加this，加了之后发现长度没问题。然后放弃治疗了，就直接提交，结果返回了一个测试用例是空串，连空串都错。

然后就瞅到创建数组的长度是n + 1，而循环初始化的是n，所以改成了n + 1。然后点调试，结果对了。。。。。。

就这？就这？？？

循环初始化for(int i = 0; i < n; ++i)，如果是空串，长度$n$就是为0，所以不会初始化第0个元素为$-1$，导致了进入dp方法时if(f[x][y] != -1)为真并返回了错误的结果。