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
------------------------------------------------------------------------------Solution #1, recursion
class Solution {
public:
bool isMatch(const char *s, const char *p) {
if (*p == '\0') {
return *s == '\0';
}
if (*(p + 1) != '*') {
return (*s == *p || (*p == '.' && *s != '\0')) && isMatch(s + 1, p + 1);
}
while (*p == *s || (*p == '.' && *s != '\0')) {
if (isMatch(s,p + 2)) {
return true;
}
s++;
}
return isMatch(s,p + 2);
}
};
Solution #2, DPdp[i][j] has the boolean value whether p[0 : i] can match s[0 : j], dp[0][0] is set to true since empty string matches empty pattern
class Solution {
public:
bool isMatch(const char *s, const char *p) {
int m = strlen(p);
int n = strlen(s);
vector<vector<bool> > dp(m + 1,vector<bool>(n + 1,false));
dp[0][0] = true;
for (int i = 2; i <= m; i++) {
if (p[i - 1] == '*' && dp[i - 2][0]) {
dp[i][0] = true;
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[i - 1] == s[j - 1] || p[i - 1] == '.') {
dp[i][j] = dp[i - 1][j - 1];
}else if (p[i - 1] == '*') {
// 1 or more char
if (dp[i][j - 1] && (p[i - 2] == s[j - 1] || p[i - 2] == '.')) {
dp[i][j] = true;
}
// zero char
else if (i - 2 >= 0 && dp[i - 2][j]) {
dp[i][j] = true;
}
}
}
}
return dp[m][n];
}
};
class Solution {
public:
bool helper(string s,string p,int i,int j) {
if (j == p.length()) return i == s.length();
if (j == p.length() - 1 || (j + 1 < p.length() && p[j + 1] != '*')) {
if (i < s.length() && (p[j] == s[i] || p[j] == '.')) {
return helper(s,p,i + 1,j + 1);
}
return false;
}
while (i < s.length() && (p[j] == s[i] || p[j] == '.')) {
if (helper(s,p,i,j + 2)) {
return true;
}
i++;
}
return helper(s,p,i,j + 2);
}
bool isMatch(string s, string p) {
return helper(s,p,0,0);
}
};
Java关键：把下一个 == '*' 和 != '*' 两种情况分开处理
class Solution {
public boolean isMatch(String s, String p) {
return rec(s,p,0,0);
}
private boolean rec(String s, String p, int i, int j) {
if (i == s.length() && j == p.length()) {
return true;
}
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
int temp = i;
while (temp < s.length() && (s.charAt(temp) == p.charAt(j) || p.charAt(j) == '.')) {
if (rec(s, p, temp + 1, j + 2)) return true;
temp++;
}
return rec(s,p,i,j + 2); // '*' matches zero chars
}
if (i < s.length() && j < p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.')) {
return rec(s, p, i + 1, j + 1);
}
return false;
}
}
预处理的时候要回头看2位之前的位置。主函数中还要考虑'*' match 0个的情况
class Solution {
public boolean isMatch(String s, String p) {
List<List<Boolean>> dp = getDP(s, p);
int m = p.length();
int n = s.length();
for (int i = 1; i <= m; i++) {
for (int j = 1; j <=n; j++) {
if (p.charAt(i - 1) == s.charAt(j - 1) || p.charAt(i - 1) == '.') {
dp.get(i).add(j, dp.get(i - 1).get(j - 1));
} else if (p.charAt(i - 1) == '*') {
if (i - 2 >= 0 && dp.get(i - 2).get(j)) {
dp.get(i).add(j, true);
}else if (dp.get(i).get(j - 1) && (p.charAt(i - 2) == s.charAt(j - 1) || p.charAt(i - 2) == '.')) {
dp.get(i).add(j, true);
}
}
}
}
return dp.get(m).get(n);
}
private List<List<Boolean>> getDP(String s, String p) {
int m = p.length();
int n = s.length();
List<List<Boolean>> dp = new ArrayList<>();
for (int i = 0; i <= m; i++) {
List<Boolean> list = new ArrayList<>();
if (i == 0 || (p.charAt(i - 1) == '*' && dp.get(i - 2).get(0))) list.add(true);
else list.add(false);
for (int j = 0; j < n; j++) {
list.add(false);
}
dp.add(list);
}
return dp;
}
}
