LeetCode 10. 正则表达式匹配

1、题目

2、分析

递归(https://labuladong.github.io/zgnb/3/17/30/)：

if (s[i] == p[j] || p[j] == '.') {
    // 匹配
    if (j < p.size() - 1 && p[j + 1] == '*') {
        // 有 * 通配符，可以匹配 0 次或多次
    } else {
        // 无 * 通配符，老老实实匹配 1 次
        i++; j++;
    }
} else {
    // 不匹配
    if (j < p.size() - 1 && p[j + 1] == '*') {
        // 有 * 通配符，只能匹配 0 次
    } else {
        // 无 * 通配符，匹配无法进行下去了
        return false;
    }
}

动态规划：

3、代码

class Solution {
    int NO_USE = -1;
    int TRUE = 1;
    int FALSE = 0;
    public boolean isMatch(String s, String p) {
        int[][] memo = new int[s.length()][p.length()];
        for(int i = 0; i < s.length(); i++){
            Arrays.fill(memo[i], NO_USE);
        }
        int res = dp(s, 0, p, 0, memo);
        return res == FALSE ? false : true;
    }

    private int dp(String s, int i, String p, int j, int[][] memo){
        int m = s.length();
        int n = p.length();
        if(i >= m){
            if((n - j) % 2 != 0) return FALSE;
            int pRes = TRUE;
            for(int k = j; k < n; k+=2){
                if(p.charAt(k + 1) != '*') pRes = FALSE;
            }
            return pRes;
        }
        if(j >= n){
            if(i == m) return TRUE;
            return FALSE;
        }
        if(memo[i][j] != NO_USE) return memo[i][j];
        if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'){
            if(j + 1 < n && p.charAt(j + 1) == '*'){
                if(dp(s, i, p, j + 2, memo) == TRUE
                   || dp(s, i + 1, p, j, memo) == TRUE){
                    memo[i][j] =  TRUE;
                    }
                else{
                    memo[i][j] =  FALSE;
                }
                return memo[i][j];
            }
            memo[i][j] = dp(s, i + 1, p, j + 1, memo);
        }else{
            if(j + 1 < n && p.charAt(j + 1) == '*'){
                memo[i][j] = dp(s, i, p, j + 2, memo);
                return memo[i][j];
            }
            memo[i][j] = FALSE;
        }
        return memo[i][j];
    }
}