• 题目

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
'’ 匹配零个或多个前面的那一个元素

• 示例

输入：s = “aa” p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。

• 算法

1. dp[i][j]下标从1到i的s的子字符串是否与下标从1到j的p的子字符串是否匹配
2. 如果p[j]！!= ‘’，若dp[i][j]为true，则要求dp[i-1][j-1]为true且p[j] == s[i]或者p[j]==’.’
   如果p[j] == '’，若dp[i][j]为true，则有两种情况（假设前面的字符为a）。
   情况1.“a”代表0个a,若dp[i][j]为true,则要求dp[i][j-2]为true
   情况2."a*"代表1个以及1个以上的a,若dp[i][j]为true，则要求dp[i-1][j-1]为true且p[j-1]s[i]或者p[j-1]’.’

• 代码

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        s = " " + s;
        p = " " + p;
        boolean dp[][] = new boolean[m+1][n+1];
        dp[0][0] = true; 
        // s串为空时，p串为a*则可匹配，所以i从0开始
        for (int i = 0; i <= m; i++) {
        	// p串为空，肯定无法匹配，所以j从1开始
            for (int j = 1; j <= n; j++) {
            	// 如果p[j]的后面是一个*,则跳过该字符的匹配
            	// 因为，要把“a*”看作一个整体处理
                if (j + 1 <= n && p.charAt(j+1) == '*') {
                    continue;
                }
                // 如果p[j]不是*，则要求最后一个字符要匹配到，剩余的其他字符要匹配
                if (i != 0 && p.charAt(j) != '*') {
                    dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
                   // 如果p[j]是*，分“a*”一次也不用，用“a*”大于等于1次两种情况
                } else if (p.charAt(j) == '*'){
                	// “a*”一次都不用，则剩余字符要匹配
                    boolean flag1 = dp[i][j-2];
                    // 如果用“a*”大于等于1次，则要求第一次用“a*”匹配,且用完“a*”后依然匹配
                    boolean flag2 = i != 0 && dp[i-1][j] 
                    	&& (p.charAt(j-1) == s.charAt(i) || p.charAt(j-1) == '.');
                    // 两种情况
                    dp[i][j] = flag1 || flag2;
                }
            }
        }
        return dp[m][n];
    }
}