4ms C++, DP to eliminate duplicate calls


  • 0
    S

    On success, we want to pop out all the way.
    On failure, record that we've been here already to avoid re-analyzing the strings.

    bool isMatch( string& s, int i, string& p, int j, vector<bool>& result ) 
     {
         int ridx;
         
         // Both empty string, complete
         if ( !s[i] && !p[j] ) return( true );
         
         // Ran out of regular expression matching
         if ( !p[j] ) return( false );
         
         // Check if we've already calculated this index
         ridx = i * p.length() + j;
         if ( result[ridx] ) return( false );
         
         if ( p[j+1] == '*' )
         {
             // Check if we match either nothing, or a single character
             if ( s[i] && ( ( p[j] == '.' ) || ( s[i] == p[j] ) ) )
             {
                 if ( isMatch( s, i, p, j+2, result ) ||
                      isMatch( s, i+1, p, j, result ) ) return( true );
             }
             // Check only if we match the skip case
             else
             {
                 if ( isMatch( s, i, p, j+2, result ) ) return( true );                
             }
         }
         // If we match a character, recurse to the next step
         else if ( ( s[i] && ( p[j] == '.' ) ) || ( s[i] == p[j] ) )
         {
             if ( isMatch( s, i+1, p, j+1, result ) ) return( true );
         }
    
         // If we got here, we weren't successful for this index
         result[ridx] = true;
         return( false );
     }
     
     bool isMatch(string s, string p) 
     {
         // s can be empty and we can still be processing p, so 1 extra row
         vector<bool> lResult( (1+s.length()) * p.length(), false );
         return( isMatch( s, 0, p, 0, lResult ) );
     }
    

Log in to reply
 

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