Regular Expression Matching

[barretlee]

本题难度：★★★

实现一个正则表达式引擎，让其支持匹配 . 和 *，其中：

• . 匹配任何单字符
• * 匹配 0 个或者多个前字符

需要匹配全部输入而非部分输入，函数格式如下：

bool isMatch(const char *s, const char *p)

如：

isMatch('aa', 'a') // false
isMatch('aa', 'aa') // true
isMatch('aaa', 'aa') // false
isMatch('aa', 'a*') // true
isMatch('aa', '.*') // true
isMatch('ab', '.*') // true
isMatch('aab', 'c*a*b') // true

参考答案：https://github.com/barretlee/daily-algorithms/blob/master/answers/6.md

[barretlee]

这道题看起来还是比较复杂的，可能出现的情况很多，不过可以通过 * 来入手分析，不管是什么字符，即便是 .，如果后面跟着的不是 *，那么匹配起来是很轻松的，可以如下穷举：

• s 为 null，p 为 null，返回 true；
• p[1] 等于 *，前部分匹配为空，则 p 前两个字符无效；前部分匹配一个字符，则进入下一次递归；
• p[1] 不等于 *，那么只需要对比第一个字符就行了，匹配通过的话，s 和 p 的前一个字符就无效了，进入下一次递归。

具体实现如下：

function isMatch(s, p) {
  if (!s && !p) return true;
  if (p && p[1] === '*') {
    return (
      // Skip First Token, Match next token
      isMatch(s, p.slice(2)) || 
      // Matched First Token, Match next token
      (s[0] === p[0] || p[0] === '.') && isMatch(s.slice(1), p)
    );
  } else {
    return (
      // Matched First Token, Match next token
      (s[0] === p[0] || p[0] === '.') && isMatch(s.slice(1), p.slice(1))
    );
  }
}

console.assert(isMatch('aa', 'a') === false, 1);
console.assert(isMatch('aa', 'aa') === true, 2);
console.assert(isMatch('aaa', 'aa') === false, 3);
console.assert(isMatch('aa', 'a*') === true, 4);
console.assert(isMatch('aa', '.*') === true, 5);
console.assert(isMatch('ab', '.*') === true, 6);
console.assert(isMatch('aab', 'c*a*b') === true, 7);

[duziaqin]

需要对.的情况再限制一下，不然在遭遇isMatch('ab', '.*c')会陷入死循环
另外返回值要求布尔值，需要稍微转一下

function isMatch(s, p) {
    if (!s && !p) return true
    if (p && p[1] === '*') {
        return !!(
            isMatch(s, p.slice(2)) ||
            (s[0] === p[0] || (p[0] === '.' && s[0])) && isMatch(s.slice(1), p)
        )
    } else {
        return !!(
            (s[0] === p[0] || (p[0] === '.' && s[0])) && isMatch(s.slice(1), p.slice(1))
        )
    }
}

[YabZhang]

def is_match(string, pattern):
    """
     1. `.`匹配任何单字；2. `*`匹配０个或多个字符；
    """
    if not string and not pattern:
        return True
    
    # `*` match blank string 
    if not string and not pattern.replace('*', ''):
        return True

    if not pattern or not string:
        return False

    if pattern[0] == '*':
        return is_match(string[1:], pattern) or is_match(string, pattern[1:])
    else:
        if pattern[0] != string[0]:
            if pattern[0] != '.':
                return False
        return is_match(string[1:], pattern[1:])


if __name__ == '__main__':
    assert is_match('aa', 'a') == False
    assert is_match('aa', 'aa') == True
    assert is_match('aaa', 'aaa') == True
    assert is_match('aaa', '.a') == False
    assert is_match('aa', '.*') == True
    assert is_match('aab', '*') == True
    assert is_match('b', '.*.') == False