LeetCode 10 Regular Expression Matching

标签: 动态规划问题 LeetCode 发布于:2020-06-07 11:16:08 编辑于:2022-02-19 20:35:59 浏览量:591

概述

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

2022年2月19日的动态规划解法

佛了,读错题目了,* 不是匹配任意值,而是匹配其之前的值的任意次。

错误理解下的解法:

class Solution {
public:
    vector<vector<int>> dp;
    string s;
    string p;
    bool isMatch(string s, string p) {
        this->s = s;
        this->p = p;
        dp.resize(s.size(), vector<int>(p.size(), -1));
        return helper(0, 0);
    }
    
    bool helper(int i, int j) {
        if (i == s.size() && j == p.size()) return true;
        if (i == s.size() || j == p.size()) return false; 
        if (dp[i][j] != -1) return dp[i][j];
        if (p[j] == '.' || p[j] == s[i]) {
            dp[i][j] = helper(i+1, j+1);
        } else if (p[j] == '*') {
            int nexti = i;
            while (nexti < s.size()) {
                dp[i][j] = helper(nexti++, j+1);
                if (dp[i][j]) break;
            }
        } else {
            dp[i][j] = false;
        }
        return dp[i][j];
    }
};

我们应当将 a* 等理解为一个特殊字符(即作为一个整体处理),这样的话,我们应该在处理当前值的时候,看一下后续值是否为 * 。

class Solution {
public:
    vector<vector<int>> dp;
    string s;
    string p;
    bool isMatch(string s, string p) {
        this->s = s;
        this->p = p;
        dp.resize(s.size(), vector<int>(p.size(), -1));
        return helper(0, 0);
    }
    
    bool helper(int i, int j) {
        if (i == s.size() && j == p.size()) return true;
        if (j == p.size()) return false; 
        if (i == s.size()) {
            // the rest must be c* pairs if it want to be true
            if (p.size() - j % 2 == 1) return false;
            for (; j + 1 < p.size(); j += 2) {
                if (p[j+1] != '*') return false;
            }
            return true;
        }
        
        if (dp[i][j] != -1) return dp[i][j];
        if (j + 1 < p.size() && p[j+1] == '*') {
            if (dp[i][j]) return true;
            if (p[j] == '.' || p[j] == s[i]) {
                int nexti = i;
                while (p[j] == '.' || p[j] == s[nexti]) {
                    if (nexti > s.size()) break;
                    dp[i][j] = helper(nexti++, j+2);
                    if (dp[i][j]) break;
                }
            } else {
                dp[i][j] = helper(i, j+2);
            }
        } else {
            if (p[j] == '.' || p[j] == s[i]) {
                dp[i][j] = helper(i+1, j+1);
            } else {
                dp[i][j] = false;
            }
        }

        return dp[i][j];
    }
};

之前想复杂了,搞了个循环出来:

int nexti = i;
while (p[j] == '.' || p[j] == s[nexti]) {
    if (nexti > s.size()) break;
    dp[i][j] = helper(nexti++, j+2);
    if (dp[i][j]) break;
}

实际上没有必要,可以用迭代的形式避免这种显式的循环:

class Solution {
public:
    vector<vector<int>> dp;
    string s;
    string p;
    bool isMatch(string s, string p) {
        this->s = s;
        this->p = p;
        dp.resize(s.size(), vector<int>(p.size(), -1));
        return helper(0, 0);
    }
    
    bool helper(int i, int j) {
        if (j == p.size()) return i == s.size(); 
        if (i == s.size()) {
            // the rest must be c* pairs if it want to be true
            if ((p.size() - j) % 2 == 1) return false;
            for (; j + 1 < p.size(); j += 2) {
                if (p[j+1] != '*') return false;
            }
            return true;
        }
        
        if (dp[i][j] != -1) return dp[i][j];
        if (j + 1 < p.size() && p[j+1] == '*') {
            if (p[j] == '.' || p[j] == s[i]) {
                dp[i][j] = helper(i, j+2) || helper(i+1, j);
            } else {
                dp[i][j] = helper(i, j+2);
            }
        } else {
            if (p[j] == '.' || p[j] == s[i]) {
                dp[i][j] = helper(i+1, j+1);
            } else {
                dp[i][j] = false;
            }
        }

        return dp[i][j];
    }
};

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