JZ52 正则表达式匹配

分类讨论一定要掌握

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        int m = str.length()+1;
        int n = pattern.length()+1;

        // dp[m][n] 代表第m，n
        boolean[][] dp =new boolean[m][n];
        dp[0][0] = true;

        //p:d*d*d*
        for(int j=2; j<=n-1; j+=2){
            dp[0][j] = dp[0][j-2] && pattern.charAt(j-1) == '*';
        }

        for(int i= 1 ; i<m; i++){
            for(int j = 1; j<n; j++){
                if(pattern.charAt(j-1) == '*'){
                    //p:d* s:d
                    if(dp[i-1][j] && pattern.charAt(j-2) == str.charAt(i-1))
                        dp[i][j] = true;
                    //p:.* s:任意字符
                    else if(dp[i-1][j] && pattern.charAt(j-2) == '.')
                        dp[i][j] = true;
                    //p:a* s:空
                    else if(dp[i][j-2]) dp[i][j] = true;
                }
                //p:. s:任意
                else if(dp[i-1][j-1] && pattern.charAt(j-1) == '.')
                    dp[i][j] = true;
                //p:a s:a 对应
                else if(dp[i-1][j-1] && pattern.charAt(j-1) == str.charAt(i-1))
                    dp[i][j] = true;
            }
        }
        return dp[m-1][n-1];
    }
}