4ms C++, DP to eliminate duplicate calls

• 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 ) );
}
``````

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