Algorithm(1)-Regular Expression Matching and Wildcard matching
Sep 9, 2018 · 2 min read
LeetCode10-Regular Expression Matching
There are two solutions for this problem.The one is Recursive, another one is Dynamic Programming.
(1)Recursive
class Solution {
public:
bool isMatch(string s, string p) {
if(p.empty()) return s.empty();
bool firstMatch = (!s.empty() && (s[0] == p[0] || p[0] == '.'));
if(p.length() >= 2 && p[1] == '*'){
return isMatch(s, p.substr(2)) || (firstMatch && isMatch(s.substr(1), p));
}
else{
return firstMatch && isMatch(s.substr(1),p.substr(1));
}
}
};However, this is not an effective way to solve the problem.Its runtime is 128ms.
(2)Dynamic Programing
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
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(p[j-1] == '*'){
dp[i][j] = (i>0 && dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.')) || dp[i][j-2];
}else{
dp[i][j] = i>0 && dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');
}
}
}
return dp[m][n];
}
};This solution performs much better, whose runtime is just 12ms.
LeetCode44-Wildcard matching
There are also two kinds of solutions, Recursive and Dynamic Programming, however, the Recursive takes too much time to get result in limited time.So just use Dynamic Programming.
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
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(p[j-1] == '*'){
//skip redundant *
if(p[j-2] == '*') dp[i][j] = dp[i][j-1];
else dp[i][j] = (i>0 && dp[i-1][j]) || (i>0 && dp[i-1][j-1]) || dp[i][j-1];
}
else{
dp[i][j] = i>0 && dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '?');
}
}
}
return dp[m][n];
}
};