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
Seen this question in a real interview before?
Yes
No
正则字符串匹配问题主要是考虑第二个字符是否为‘*’，如果不是，那就先判断第一个字符是否匹配，然后调用递归函数进行子串的判断；如果第二个字符是‘*’，那么会复杂些，首先考虑‘*’之前的字符出现0次的情况，其次再考虑至少出现一次的情况，也就是进行递归调用，s去掉第一个字符，p不能去掉第一个字符，因为‘*’之前的字符可以有无限个
代码如下：
1 class Solution { 2 public: 3 bool isMatch(string s, string p) { 4 if (p.empty()) return s.empty(); 5 if (p.size() > 1 && p[1] == '*') { 6 return isMatch(s, p.substr(2)) || (!s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p)); 7 } else { 8 return !s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1)); 9 } 10 }
还有一种是动态规划算法，用空间换时间，讲真，这部分我不是特别理解。定义一个二维的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.
1 class Solution { 2 public: 3 bool isMatch(string s, string p) { 4 int m = s.size(), n = p.size(); 5 vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false)); 6 dp[0][0] = true; 7 for (int i = 0; i <= m; ++i) { 8 for (int j = 1; j <= n; ++j) { 9 if (j > 1 && p[j - 1] == '*') { 10 dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]); 11 } else { 12 dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.'); 13 } 14 } 15 } 16 return dp[m][n]; 17 } 18 };