题目:实现正则表达式的.和*两个符号。

思路:第一时间看到正则,马上就想到了用while来不停匹配。后来遇到了a*a匹配aa,发现要处理贪心和不贪心多种情况,所以将while转为了递归。

题目考察的多是递归的设计和考虑多种情况是否周全,代码很少(JS实现):

var isMatch = function(s, p) {
    
    if (!p) return !s;
    
    let match = !!s && (s[0] === p[0] || p[0] === ".");
    // console.log(s, p, match)
    
    if (p[1] === "*") {
        return isMatch(s, p.substr(2)) || (match && isMatch(s.substr(1), p));
    } else {
        return match && isMatch(s.substr(1), p.substr(1))
    }
};

如果觉得递归代码不好看,可以将递归改为动态规划,使用bottom-up或者简单的memo来提高程序的性能。

分类: 算法

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注