LeetCode 10 Regular Expression Matching

Tag: LeetCode 动态规划 Posted on 2020-06-07 11:16:08 Edited on 2020-06-07 11:17:21 Views: 8

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];
    }
}

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