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
这道求正则表达式匹配的题和那道 Wildcard Matching 通配符匹配的题很类似，不同点在于*的意义不同，在之前那道题中，*表示可以代替任意个数的字符，而这道题中的*表示之前那个字符可以有0个，1个或是多个，就是说，字符串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的结果
解法一：
class Solution { public: bool isMatch(string s, string p) { if (p.empty()) return s.empty(); if (p.size() == 1) { return (s.size() == 1 && (s[0] == p[0] || p[0] == '.')); } if (p[1] != '*') { if (s.empty()) return false; 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; s = s.substr(1); } return isMatch(s, p.substr(2)); } };
上面的方法可以写的更加简洁一些，但是整个思路还是一样的，我们先来判断p是否为空，若为空则根据s的为空的情况返回结果。当p的第二个字符为*号时，由于*号前面的字符的个数可以任意，可以为0，那么我们先用递归来调用为0的情况，就是直接把这两个字符去掉再比较，或者当s不为空，且第一个字符和p的第一个字符相同时，我们再对去掉首字符的s和p调用递归，注意p不能去掉首字符，因为*号前面的字符可以有无限个；如果第二个字符不为*号，那么我们就老老实实的比较第一个字符，然后对后面的字符串调用递归，参见代码如下：
解法二：
class Solution { public: 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)); } } };
我们也可以用DP来解，定义一个二维的DP数组，其中dp[i][j]表示s[0,i)和p[0,j)是否match，然后有下面三种情况(下面部分摘自这个帖子)：
1. P[i][j] = P[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
2. P[i][j] = P[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
3. P[i][j] = P[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.
解法三：
class Solution { public: 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) { for (int j = 1; j <= n; ++j) { if (j > 1 && 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]; } };
本文转自博客园Grandyang的博客，原文链接：正则表达式匹配[LeetCode] Regular Expression Matching ，如需转载请自行联系原博主。
