自己解法

这个题有的印象是，用动态规划，p的某一位要判断是否是*。

p不是*的情况下，解法简单，dp[i][j] = dp[i - 1][j - 1] && i 和 j位置上的元素相等或j为？可以匹配任意单字符。

p是* 的情况下，分为使用*和不使用*的情况：

使用*：dp[i][j] = dp[i-1][j]，这个本来理解的是，dp[i][j] = dp[i-1][j-1]，这种情况下是使用了*，

但是，这个*有可能是代表多个字符，也就是说在这次匹配之前就已经使用了*，这种情况下dp[i][j]应该等于dp[i-1][j]。

不使用*：dp[i][j]=dp[i][j-1]，也就是说i和j-1的位置已经匹配不用再要*了。

小结：二维数组的动态规划问题，一般都是一层一层铺开的，所以这点决定了数组的生成方式，我最开始是陷进了dp[i][j] = dp[i-1][j-1]的怪圈，这样只能拿对角线的值了，尴尬。

class Solution {

    public boolean isMatch(String s, String p) {

        int sLen = s.length();

        int pLen = p.length();

        boolean[][] dp = new boolean[sLen + 1][pLen + 1]; 

        dp[0][0] = true;

        for (int i = 1; i <= pLen; i++) {

            if (p.charAt(i - 1) == '*') {

                dp[0][i] = true;

            } else {

                break;

            }

        }

        for (int i = 1; i <= sLen; i++) {

            for (int j = 1; j <= pLen; j++) {

                if (p.charAt(j - 1) != '*') {

                    dp[i][j] = dp[i - 1][j - 1] 

                        && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?');

                } else {

                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];   

                }

            }

        }

        return dp[sLen][pLen];       

    }

}

官方解法：

自己解法参考官方，不再赘述