[数据结构与算法]10. 正则表达式匹配（动态规划）

package com.mt.wsq.lc.dp;

/**
 * 10. 正则表达式匹配
 *
 * @author wangshiqiang03
 * @date 2021/8/13
 *
 * https://leetcode-cn.com/problems/regular-expression-matching/
 */
public class IsMatch {
    /**
     * 整体思想：化整为零，采用逐个位置进行匹配
     * 定义状态：那些是变化的值，这道题很明显就是s和p字符串的长度，因此定义状态为f[i][j]
     *      f[i][j]表示字符串p前j个字符与字符串s前i个字符的匹配情况
     * 状态转移方程：
     *      以字符串p中第j个字符作为分情况讨论：
     *      1. p[j] 为普通字符，所以当p[j]==s[i]时，f[i][j] = f[i-1][j-1]; 当p[j] != s[i]时，f[i][j] = false;
     *      2. p[j] 为'.'字符，表示匹配所有字符，索引f[i][j] = f[i-1][j-1]
     *      3. p[j] 为'*'字符，*表示能匹配前一个字符0或多个，因此需要看j-1字符的情况：
     *          匹配0个情况：f[i][j] = f[i][j-2]
     *          第j-1字符为普通字符：如果p[j-1] == s[i]，那么f[i][j] = f[i][j] || f[i-1][j],(由于*可以匹配多次)
     *          第j-1字符为'.'字符：f[i][j] = f[i][j] || f[i-1][j],(由于*可以匹配多次)
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch(String s, String p){
        if (s == null && p == null){
            return true;
        }
        if (s == null || p == null){
            return false;
        }
        int m = s.length();
        int n = p.length();
        char[] sArr = s.toCharArray();
        char[] pArr = p.toCharArray();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;

        for (int i = 0; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if (pArr[j - 1] == '*'){
                    f[i][j] = f[i][j-2];
                    if (matcher(sArr, pArr, i, j - 1)){
                        f[i][j] = f[i][j] || f[i-1][j];
                    }
                }else{
                    if (matcher(sArr, pArr, i, j)){
                        f[i][j] = f[i-1][j-1];
                    }
                }
            }
        }
        return f[m][n];
    }
    public boolean matcher(char[] sArr, char[] pArr, int i, int j){
        if (i == 0){
            return false;
        }

        if (pArr[j-1] == '.'){
            return true;
        }
        return sArr[i-1] == pArr[j-1];
    }
}