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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
     /**
        思路：
        创建二维dp ， dp[i][j] 表示str前i位 与 pattern前j位是否匹配

        1.如果str[i] == pattern[j] || pattern[j] == "."
        表示匹配 那么它的状态取决于它的上一个状态 dp[i][j] = dp[i-1][j-1]
        如果不满足上面的状态 那么判断 当前pattern[j]是否为*
        如果是* 那么还是可以发生状态转移
        2.1如果 pattern[j] == "*" && pattern[j-1]==str[i]
        那么表示 例如a* 可以匹配0个字符、1个字符、多个字符
        2.1.1如果 a*匹配的是0个字符
        那么 dp[i][j] = dp[i][j-2]   #pattern去掉 一个* 和一个 a
        2.1.2如果 a*只匹配1个字符 例如 a*匹配a
        那么 dp[i][j] = dp[i-1][j-2]  #既然匹配了 则要判断上次状态
        2.1.3如果 a*匹配多个字符  例如 a*匹配aaa...
        那么 dp[i][j] = dp[i-1][j]   #str去掉一个字符 再次判断上一次状态 直到判断到2.2为止
        2.2如果 pattern[j] == "*"  但是 pattern[j-1]!=str[i] 表示0次匹配
        dp[i][j] = dp[i][j-2]
        3.如果1、2条件都不满足表示不能发生匹配 则默认false 然后continue；
        
     
      */
    public boolean match (String str, String pattern) {
        // write code here
        int m = str.length();
        int n = pattern.length();


        //创建二维状态dp
        boolean dp[][] = new boolean[m+1][n+1];

        //当字符串 和 正则式都为空时 匹配成功
        dp[0][0] = true;

        //初始化dp
        //1.当str不为空 pattern为空时 匹配失败 默认false
        //2.当str为空 pattern不为空时 要判断是否有* 且只会发生空匹配

        for(int i = 1 ; i <= n ; i++){
            if(i >= 2 && 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(str.charAt(i-1) == pattern.charAt(j-1) || pattern.charAt(j-1)=='.'){
                    dp[i][j] = dp[i-1][j-1];
                }else if(j >= 2 && pattern.charAt(j-1) == '*'  ){
                    if(str.charAt(i-1) == pattern.charAt(j-2) || pattern.charAt(j-2) == '.'){
                        //可能发生0次 | 1次 |多次 匹配
                        dp[i][j] = dp[i][j-2] | dp[i-1][j-2] | dp[i-1][j];
                    }else{
                        dp[i][j] = dp[i][j-2];
                    }
                }else{
                    continue;
                }
            }
        }


        return dp[m][n];
    }
}