题解 | #正则表达式匹配#

正则表达式匹配

http://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4

动规

class Solution {
public:
    bool isMatch(const string s, const string p, int i, int j){
        if(p[j - 1] == '.') return true;
        return s[i - 1] == p[j - 1];
    }
    bool match(string s, string p) {
        int m = s.length(), n = p.length();
        bool dp[m + 1][n + 1];
        memset(dp, false, sizeof(dp));
        dp[0][0] = true;
        for(int j = 2; j <= n; j ++){ //i从0开始,因为'a*'这种情况,可以匹配空串
            if(p[j - 1] == '*') dp[0][j] = dp[0][j - 2];
        }
        for(int i = 1; i <= m; i ++){ 
            for(int j = 1; j <= n; j ++){
                if(p[j - 1] == '*'){
                    dp[i][j] |= dp[i][j - 2]; //*匹配0次
                    if(isMatch(s, p, i, j - 1)) dp[i][j] |= dp[i - 1][j];
                }else{
                    if(isMatch(s, p, i, j)) dp[i][j] |= dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};
全部评论

相关推荐

Java抽象带篮子:简历怎么写可以看看我发的帖子,你的第一个是实习经历吗?那怎么写的是你的第一个练手项目呢?简历写的怎么样直接投小厂面试一下就知道了
没有实习经历,还有机会进...
点赞 评论 收藏
分享
06-11 17:39
门头沟学院 Java
小呆呆的大鼻涕:卧槽,用户彻底怒了
点赞 评论 收藏
分享
ohs的小木屋:比不少实习待遇高了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务