剑指offer-52-正则表达式

思路

本题太绕了，总体上动态规划
当前如果pat[j]=str[i],或者pat[j]='.',那么刚好就是消去，dp[i][j]=dp[i-1][j-1]
主要是当前是*，这个时候分为匹配0次，匹配1次，匹配多次，不匹配四种情况。

代码

public class Solution {
    public boolean match(char[] str, char[] pattern){
        boolean[][] dp = new boolean[str.length + 1][pattern.length + 1];
        dp[0][0] = true;
        for (int i = 1; i < dp[0].length; i ++) {
            if(pattern[i - 1] == '*') dp[0][i] = dp[0][i - 2];
        }
        for (int i = 1; i < dp.length; i ++) {
            for (int j = 1; j < dp[0].length; j ++) {
                //模式串当前字符匹配str[i-1]
                if(pattern[j - 1] == '.' || pattern[j - 1] == str[i - 1]) dp[i][j] = dp[i - 1][j - 1];
                else if(pattern[j - 1] == '*') {
                    //当前是*，如果模式串前一个与str[i-1]匹配，dp[i][j-2]表示匹配0次，dp[i][j-1]表示匹配1次
                    // dp[i-1][j] 表示多次，str这个字符一对多。
                    if(pattern[j - 2] == str[i - 1] || pattern[j - 2] == '.'){
                        dp[i][j] = dp[i][j - 1] || dp[i][j - 2] || dp[i - 1][j];
                    }else{
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }
        return dp[str.length][pattern.length];
    }    
}