10.正则表达式匹配 (Hard)*

题目描述*

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

示例*

s = "aab"

p = "c*a*b"

提示*

s 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

代码*

动态规划之正则表达

虽然学过动态规划，但是看到这个题还是有点发怵。跟随带哥的文章学习螺旋上升的算法学习过程。

首先，从普通的字符串比较出发：

bool isMatch(string text, string pattern) {
    if(text.length() != pattern.length()) {
        return false;
    }
    for(int i = 0; i < pattern.length(); i++) {
        if(pattern[i] != text[i]) {
            return false;
        }
    }
    return true;
}

之后我们尝试把这个代码改为递归的形式，正则匹配将基于递归的框架实现。

bool isMatch(string text, string pattern) {
    if(pattern.length() == 0) {
        return text.length() == 0;
    }
    bool firstMatch = (text.length() != 0 && text[0] == pattern[0]);
    return firstMatch && isMatch(text.substr(1), pattern.substr(1));
}

在这个框架的基础上我们一步步实现正则匹配，首先对于 . 的实现，匹配任意字符：

bool isMatch(string text, string pattern) {
    if(pattern.length() == 0) {
        return text.length() == 0;
    }
    bool firstMatch = (text.length() != 0 && (pattern[0] == '.' || pattern[0] == text[0]));
    return firstMatch && isMatch(text.substr(1), pattern.substr(1));
}

接下来处理 * 的实现，匹配前一个字符任意次数，包括零次，我们不能确定到底是几次，不过对于递归，我们只需要处理当前的情况：

递归dp

bool isMatch(string text, string pattern) {
    if(pattern.length() == 0) {
        return text.length() == 0;
    }
    bool firstMatch = (text.length() != 0 && (pattern[0] == '.' || pattern[0] == text[0]));
    if(pattern.length() >= 2 && pattern[1] == '*') {
        // 当前字符后面出现了 *
        // 选择匹配零次，即跳过 pattern 的这两个字符
        // 选择匹配一次，text 前进一个字符
        return isMatch(text, pattern.substr(2)) || 
            (firstMatch && isMatch(text.substr(1), pattern));
    }else {
        return firstMatch && isMatch(text.substr(1), pattern.substr(1));
    }
}

到这其实我们就实现了正则匹配的功能。我们可以通过动态规划的思路来优化这个问题，避免子字符串重复划分。

dp[i + 1][j + 1] 表示 text 的前 i 个是否能被 pattern 的前 j 个匹配。

class Solution {
public:
    bool isMatch(string text, string pattern) {
        int lenText = text.length(), lenPattern = pattern.length();
        vector<vector<bool>> dp(lenText + 1, vector<bool>(lenPattern + 1, false));
        dp[0][0] = true;
        // 初始化 为了匹配空串
        for(int i = 1; i < lenPattern; i++) {
            if(pattern[i] == '*' && dp[0][i - 1]) {
                dp[0][i + 1] = true;
            }
        }
        for(int i = 0; i < lenText; i++) {
            for(int j = 0; j < lenPattern; j++) {
                if(text[i] == pattern[j] || pattern[j] == '.') {
                    dp[i + 1][j + 1] = dp[i][j];
                }else if(pattern[j] == '*') {
                    if(pattern[j - 1] == '.' || text[i] == pattern[j - 1]) {
                        dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j - 1];
                    }else {
                        dp[i + 1][j + 1] = dp[i + 1][j - 1];
                    }
                }
            }
        }
        return dp[lenText][lenPattern];
    }
};

最后更新: July 23, 2022