Leetcode—10.正则表达式匹配【困难】

2023每日刷题（五十八）

Leetcode—10.正则表达式匹配

算法思想

参考题解

实现代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for(int j = 1; j <= n; j++) {
            if(p[j - 1] == '*') {
                // s为空字符串的时候, *匹配0个元素, 例如"a*" = ""
                dp[0][j] = dp[0][j - 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] == '*') {
                    // *匹配0次
                    if(s[i - 1] != p[j - 2] && p[j - 2] != '.') {
                        dp[i][j] = dp[i][j-2];
                        // *匹配多次
                    } else {
                        dp[i][j] = dp[i][j-2] || dp[i-1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
};

运行结果

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！