0010. 正则表达式匹配

[utterances-bot]

0010. 正则表达式匹配 | 算法通关手册

10. 正则表达式匹配 # 标签：递归、字符串、动态规划 难度：困难 题目大意 # 描述：给定一个字符串 s 和一个字符模式串 p。 要求：实现一个支持 '.' 和 '*' 的正则表

https://algo.itcharge.cn/Solutions/0001-0099/regular-expression-matching/

[S1mpleBug]

附上C++代码

• 参考题解🔗

const int N = 33;
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        bool dp[N][N] = {false};
        dp[0][0] = true;
        for(int i = 1; i <= n; ++i) if(p[i-1] == '*') dp[0][i] = dp[0][i-2];
        for(int i = 1; i <= m; ++i) {
            for(int j = 1; j <= n; ++j) {
                if(s[i-1] == p[j-1] || p[j-1] == '.')
                    dp[i][j] = dp[i-1][j-1];
                else if(p[j-1] == '*') {
                    if(s[i-1] != p[j-2] && p[j-2] != '.')
                        dp[i][j] = dp[i][j-2];
                    else
                        dp[i][j] = dp[i-1][j] | dp[i][j-2];
                }
            }
        }
        return dp[m][n];
    }
};