题解 | #正则表达式匹配#TOP76

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @param pattern string字符串
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        // write code here
        if (str == null || pattern == null) {
            return false;
        }
        int m = str.length();
        int n = pattern.length();
        //dp[i][j] 表示 str[0,i-1] 字符和 pattern[0,j-1]是否匹配
        //前 i 个字符 和  pattern的前j个是否匹配
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
         
        for(int i = 2; i<= n ; i++){
            if(pattern.charAt(i-1) == '*'){
                //匹配前面任意字符，可出现多次,空字符串想要匹配成功，只能把前一个字符去掉
                dp[0][i] = dp[0][i-2];
            }
        }
        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n ; j++) {
               
                if (pattern.charAt(j - 1) != '*') {
                    //不是匹配前面的任意字符
                    //if 判断 匹配条件 能匹配组
                    //如果 str[i-1] == pattern[j-1] i肯定要大于0
                    //如果不相等，或者patter[j-1] = '.' 匹配任意一个字符
                    if (i > 0 && (str.charAt(i - 1) == pattern.charAt(j - 1) ||
                                  pattern.charAt(j - 1) == '.')) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else {
                    //如果是 * 匹配前面任意字符 包含0次
                    if (j >= 2) {
                        //parttern j-1前面字符出现1次 str[0,i-1] 和 partenr[0, j-2] j-2只出现一次(*号代表一次)
                        if (i >= 1  &&
                                (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.')
                           ) {
                            // 如果i - 1 位置能和j-2位置匹配上，那么问题转换成看str1[0,i-2] 到 patternp[0, j-1] 因为是*是可以匹配任意字符的呀，所以是J-1
                            //能匹配上，* 号是可以让字符多出现一次所以是dp[i-1][j] 也可以不出现 dp[i][j-2]
                            dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
                        } else {
                            //因为*可以匹配0次，也就是去掉前面的字符partern[j-2]，看下能不能和partern[0,j-3]匹配 aadbc  aa*c
                            dp[i][j] = dp[i][j - 2];
                        }
                    }

                }
            }
        }
        return dp[m][n];
    }
}