https://leetcode.com/problems/regular-expression-matching/

状态：dp[i][j] 是一个布尔数组，表示 string[i:] 和 pattern[j:] 能否匹配成功。

选择：对于 pattern 中的字母和 . 并没有选择可言；对于 *，我们可以选择匹配其之前的字母 0~N 次，放到递归中则是匹配或者不匹配。

1. 匹配：则 pattern 保持不变，string 进一位。
2. 不匹配，则 string 保持不变，pattern 进两位（因为 * 和其之前的字符为一个整体）。

注意：

1. 为了代码的可读性，使用一个专门的布尔数组来记录 memory 中是否有之前计算过的值。
2. 注意需要妥善处理边界情况。

代码：

class Solution {
    String s, p;
    boolean[][] data;
    boolean[][] computed;
    public boolean isMatch(String s, String p) {
        this.s = s;
        this.p = p;
        data = new boolean[s.length()+1][p.length()+2];
        computed = new boolean[s.length()+1][p.length()+2];
        return dp(0, 0);
    }

    private boolean dp(int i, int j) {
        // When pattern is over, return true if the string also is over.
        if(j>=p.length()) return i>=s.length();
        boolean current = false;
        if(i<s.length()) {
            if(computed[i][j]) return data[i][j];
            current = (s.charAt(i) == p.charAt(j)) || (p.charAt(j) == '.');
        }
        // Notice the * pattern must act with its previous character.
        if(p.length() > j+1 && p.charAt(j+1) == '*') data[i][j] = dp(i, j+2) || (current && dp(i+1, j));
        else data[i][j] = current && dp(i+1, j+1);
        computed[i][j] = true;
        return data[i][j];
    }
}

Links: LeetCode-474-Ones-and-Zeroes

未经允许，禁止转载，本文源站链接：https://iamazing.cn/