LeetCode 10. Regular Expression Matching

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

思路：第一时间看到正则，马上就想到了用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来提高程序的性能。