My simple recursive solution with explanation( run time 3 ms)


  • 0
    R

    The idea here is basically to see that from given index in pattern and given index in our string if there is a possibility that we may be able to generate our string.
    Consider a function match(int i,int j,string p,string s) which returns true if you can generate the string s from index j by being at index i in pattern.
    Few cases need to be considered (which I have in my solution ):-
    1.Base cases:-
    (a)If we reach the end of both string and pattern then we have successfully generated the string.(i,e, if(i==p.size() and j==s.size()) return true
    (b)If we have only reached the end of string but not our pattern then if:
    (i)the given index in pattern is not length(pattern) -1 and at the next index in
    pattern we have a '*' then increment the index of pattern and check again.

    (ii)Else string can not be generated so return false.
    
    1. If current index of p ,ie, i<p.size()-1 and p[i+1]=='*' ,then we have two choices either keep the current index same and increment index of string or ignore the current and its next index ,i,e, ignore the current character to be matched. Again we recursively check and if either way we get a true,then we return true.
      3.If above conditions are not satisfied then:
      (a) If p[i]==s[j] or p[i]=='.' ,means we go one step further then we check for match(i+1,j+1,p,s)
      4.Finally if nothing matches then return false
      .
      Finally you need to do some memoization.
    bool match(int i,int j,string &p,string &s,vector<vector<int> >&dp)
        {
            if(i==p.size()&&j==s.size()) return true;
            int &ans=dp[i][j];
            if(ans!=-1)    return dp[i][j];
            if(j==s.size())
            {
                if((i+2)<=p.size()&&p[i+1]=='*') return dp[i][j]=match(i+2,j,p,s,dp);
                else return false;
            }
            if((i+1)<p.size()&&p[i+1]=='*')
            {
                if(p[i]=='.'||p[i]==s[j])
                 return ans=(match(i,j+1,p,s,dp)||match(i+2,j,p,s,dp)||match(i+2,j+1,p,s,dp));
                else return ans=match(i+2,j,p,s,dp);
            }
            
            if(p[i]=='.'||p[i]==s[j])
                return ans=match(i+1,j+1,p,s,dp);
            return ans=false;
        }
        bool isMatch(string s, string p) {
            int n=p.size(),m=s.size();
            vector<vector<int> >dp(n+1,vector<int>(m+1,-1));
            return match(0,0,p,s,dp);
        }
    

    This is my first post. I just felt like sharing it. I would be glad to have suggestions to improve the code:)


Log in to reply
 

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