Regular Expression Matching
Given an input string (s) and a pattern (p), 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).
Note:
- s could be empty and contains only lowercase letters a-z.
- p could be empty and contains only lowercase letters a-z, and characters like . or *.
思路一：递归
class Solution {
public:
bool isMatch(const string& s, const string& p) {
return isMatch(s.c_str(), p.c_str());
}
private:
bool matchFirst(const char *s, const char *p) {
return *p == *s || (*p == '.' && *s != '\0');
}
bool isMatch(const char *s, const char *p) {
if (*p == '\0') return *s == '\0'; //empty
// next char is not '*', then must match current character
if (*(p + 1) != '*') {
if (matchFirst(s, p)) return isMatch(s + 1, p + 1);
else return false;
} else { // next char is '*'
if (isMatch(s, p + 2)) return true; // try the length of 0
while ( matchFirst(s, p) ) // try all possible lengths
if (isMatch(++s, p + 2)) return true;
return false;
}
}
};
时间复杂度o(n),空间复杂度o(1)
思路二：动态规划
状态方程
class Solution {
public:
bool isMatch(string s, string p) {
/**
* f[i][j]: if s[0..i-1] matches p[0..j-1]
* if p[j - 1] != '*'
* f[i][j] = f[i - 1][j - 1] && s[i - 1] == p[j - 1]
* if p[j - 1] == '*', denote p[j - 2] with x
* f[i][j] is true iff any of the following is true
* 1) "x*" repeats 0 time and matches empty: f[i][j - 2]
* 2) "x*" repeats >= 1 times and matches "x*x": s[i - 1] == x && f[i - 1][j]
* '.' matches any single character
*/
int m = s.size(), n = p.size();
vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
f[0][0] = true;
// Deals with patterns like a* or a*b*c*
for (int j = 1; j <= n; j++)
f[0][j] = '*' == p[j - 1] && f[0][j - 2];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (p[j - 1] != '*')
f[i][j] = f[i - 1][j - 1] && (s[i - 1] == p[j - 1] || '.' == p[j - 1]);
else
// p[0] cannot be '*' so no need to check "j > 1" here
f[i][j] = f[i][j - 2] || (s[i - 1] == p[j - 2] || '.' == p[j - 2]) && f[i - 1][j];
return f[m][n];
}
};
时间复杂度o(mn),空间复杂度o(mn)