# Two solutions - Recursive and DP both can be converted to each other easily- C++

• Recursive approach:

``````        class Solution {
public:
bool helper(string s, int si, string p, int pi){
if(si == s.size() && pi == p.size()) return true;

if(p[pi+1] == '*'){
return helper(s,si,p,pi+2) ||  //match the zero occurence case
((s[si]==p[pi] || p[pi]=='.') && si<s.size() && helper(s,si+1,p,pi)); //match 1 or more occurence case
}else{
return (si<s.size() && (s[si]==p[pi] || p[pi]=='.')) && helper(s, si+1, p, pi+1); //match char by char case
}
}

bool isMatch(string s, string p) {
return helper(s,0,p,0);
}
};
``````

Dynamic programming solution:

``````    int m = s.size(), n = p.size();
vector<vector<bool>> _ismatch(m + 1, vector<bool>(n + 1));
_ismatch[0][0] = true;

for(int j = 1; j <=n; j++){
if(p[j-1] == '*')
_ismatch[0][j] = (j>1 &&_ismatch[0][j-2]);
}

for(int i =1; i<=m; i++){
for(int j =1; j<=n; j++){
if(p[j-1] == '*')
_ismatch[i][j] = (j>1 &&_ismatch[i][j-2]) || (_ismatch[i-1][j]&&(p[j-2]==s[i-1] || p[j-2]=='.'));
else{
_ismatch[i][j] = (s[i-1] == p[j-1] || p[j-1] == '.') && _ismatch[i-1][j-1];
}
}
}
return _ismatch[m][n];

}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.