10. Regular Expression Matching (Hard)

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
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

Note:

s is the origianl string, p is its regular expression.

Solution 1: recursive (163 ms)

Problem: too much stack, very slow

这道求正则表达式匹配的题和那道 Wildcard Matching 通配符匹配的题很类似，不同点在于*的意义不同，在之前那道题中，*表示可以代替任意个数的字符，而这道题中的*表示之前那个字符可以任意个，就是说，字符串a*b，可以表示b或是aaab，即a的个数任意，这道题的难度要相对之前那一道大一些，分的情况的要复杂一些，需要用递归Recursion来解，大概思路如下：

• 若p为空，若s也为空，返回true，反之返回false

• 若p的长度为1，若s长度也为1，且相同或是p为'.'则返回true，反之返回false

• 若p的第二个字符不为*，若此时s为空返回false，否则判断首字符是否匹配，且从各自的第二个字符开始调用递归函数匹配

• 若p的第二个字符为*，若s不为空且字符匹配，调用递归函数匹配s和去掉前两个字符的p，若匹配返回true，否则s去掉首字母

• 返回调用递归函数匹配s和去掉前两个字符的p的结果

bool isMatch(string s, string p) {
    if (p.empty()) return s.empty();
    if (p.size() == 1) return (s.size() == 1 && (p[0] == s[0] || p[0] == '.'));

    // '..'
    if (p[1] != '*') {
        if (s.empty()) return false;
        // check first char, skip this position and recursion
        return (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
    }

    // '.*'
    while (!s.empty() && (s[0] == p[0] || p[0] == '.')) {
        if (isMatch(s, p.substr(2))) return true; // the prefix of s is matched with '.*', check the rest
        s = s.substr(1); // add one more char as the prefix of s
    }

    return isMatch(s, p.substr(2));
}

上面的方法可以写的更加简洁一些，但是整个思路还是一样的，我们先来判断p是否为空，若为空则根据s的为空的情况返回结果。当p的第二个字符为号时，由于号前面的字符的个数可以任意，可以为0，那么我们先用递归来调用为0的情况，就是直接把这两个字符去掉再比较，或者当s不为空，且第一个字符和p的第一个字符相同时，我们再对去掉首字符的s和p调用递归，注意p不能去掉首字符，因为*号前面的字符可以有无限个；如果第二个字符不为*号，那么我们就老老实实的比较第一个字符，然后对后面的字符串调用递归，参见代码如下：

bool isMatch(string s, string p) {
    if (p.empty()) return s.empty();
    if (p.size() > 1 && p[1] == '*') 
        return isMatch(s, p.substr(2)) || (!s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p));
    else
        return !s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
}

Solution 2: DP 15ms

我们也可以用DP来解，定义一个二维的DP数组，其中dp[i][j]表示s[0,i)和p[0,j)是否match，然后有下面三种情况：

1.  dp[i][j] = dp[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
2.  dp[i][j] = dp[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
3.  dp[i][j] = dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern repeats for at least 1 times.

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 i = 0; i <= m; ++i) {
        // skip: p.size() == 0 && s.size() != 0, always false
        for (int j = 1; j <= n; ++j) {
            if (p[j-1] == '*') {
                dp[i][j] = dp[i][j-2] || (i > 0 && (s[i-1] == p[j-2] || p[j-2] == '.') && dp[i-1][j]);
            } else {
                dp[i][j] = i > 0 && dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');
            }
        }
    }

    return dp[m][n];
}