Algorithm(1)-Regular Expression Matching and Wildcard matching

Lee amileln
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];
}
};
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade