C++ DP O(mn) Solution with Illustration, Easy to Understand


  • 1

    Straight forward DP, the key point is to figure out the equation. Transformed is the string p without '*', star is an array to bookkeep stars. The equation(the core of this algorithm) is

    if(table[i-1][j-1]) // peek upper left
      if(transformed[j-1]=='.'||transformed[j-1]==s[i-1])
        table[i][j]=true;
    if(table[i-1][j]&&star[j-1]) // peek up 
      if(transformed[j-1]=='.'||transformed[j-1]==s[i-1])
        table[i][j]=true;
    if(table[i][j-1]&&star[j-1]) // look left
      table[i][j]=true;
    

    For example: s is "aaa", p is "ab*a*c*a"
    The table looks like

             *  *  *
       p  a  b  a  c  a
    s  T  F  F  F  F  F
    a  F  T  T  T  T  F
    a  F  F  F  T  T  T
    a  F  F  F  T  T  T
    
    bool isMatch(string s, string p) {
            string transformed;
            vector<bool> star;
            int i=0;
            // Transform
            while(i<p.size()) {
                if(p[i]!='*')
                    transformed.push_back(p[i]);
                if((i+1)<p.size() && p[i+1]=='*') {
                    star.push_back(true);
                    i++;
                }
                else
                    star.push_back(false);
                i++;
            }
            // Initialize table
            vector<vector<bool>> table(s.size()+1,vector<bool>(transformed.size()+1,false));
            int j=1;
            table[0][0]=true;
            while(j<=transformed.size() && star[j-1])
                table[0][j++]=true;
            // Fill up table
            for(i=1;i<=s.size();i++)
                for(j=1;j<=transformed.size();j++) {
                    if(table[i-1][j-1]) // peek upper left
                        if(transformed[j-1]=='.'||transformed[j-1]==s[i-1])
                            table[i][j]=true;
                    if(table[i-1][j]&&star[j-1]) // peek up 
                        if(transformed[j-1]=='.'||transformed[j-1]==s[i-1])
                            table[i][j]=true;
                    if(table[i][j-1]&&star[j-1]) // look left
                        table[i][j]=true;
                }
            return table[s.size()][transformed.size()];
        }
    

Log in to reply
 

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