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


  • 0

    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];
        
            }

Log in to reply
 

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