C++ bottom-up solution using dynamic programming (3ms)


  • 0
    A
    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            
            // Edge cases
            if( s3.length() != s1.length() + s2.length() )
                return false; // no way to interleave
            if( s3 == s1 + s2 || s3 == s2 + s1 )
                return true; // trivial concatenation
            
            // Create space for memo, and initialize all entries to false
            bool** memo = new bool*[ s1.length() + 1 ];
            for( int i = 0; i <= s1.length(); ++i ) {
                memo[i] = new bool[ s2.length() + 1 ];
                for( int j = 0; j <= s2.length(); ++j )
                    memo[i][j] = false;
            }
            
            // memo[i][j] = can we interleave s1[i:] and s2[j:] to get s3[i + j:]?
            
            // Base cases:
            // 1. memo[length of s1][length of s2] = true, because we can get "" by interleaving "" and ""
            // 2. We also have memo[length of s1][i] = (s3[length of s1 + i:] == s2[i:]) and similar s1 <--> s2
            
            memo[ s1.length() ][ s2.length() ] = true; // empty strings interleaved produces empty string
            int k = 0;
            while( s3[ s3.length() - 1 - k] == s2[ s2.length() - 1 - k]  && k < s2.length() ) {
                memo[ s1.length() ][ s2.length() - 1 - k ] = true;
                ++k;
            }
            k = 0;
            while( s3[ s3.length() - 1 - k] == s1[ s1.length() - 1 - k] && k < s1.length() ) {
                memo[ s1.length() - 1 - k ][ s2.length() ] = true;
                ++k;
            }
            
            // The recurrence rule is that we can interleave s1[i:] and s2[j:] to get s3[i + j: ] iff either
            //      s1[i] == s3[i + j] and we can interleave s1[i + 1:] and s2[j:] to get s3[i + j + 1:], or
            //      s2[j] == s3[i + j] and we can interleave s1[i:] and s2[j + 1:] to get s3[i + j + 1:].
            // We just apply this recurrence.
            for( int i = s1.size() - 1; i >=0; --i )
                for( int j = s2.size() - 1; j >= 0; --j ) {
                    memo[i][j] = ( s3[i + j] == s2[j] && memo[i][j + 1] ) || ( s3[i + j] == s1[i] && memo[i + 1][j] );
                }
            
            bool result = memo[0][0];
            
            // Deallocate memory
            for( int i = 0; i <= s1.size(); ++i )
                delete[] memo[i];
            delete[] memo;
            
            return result;
        }
    };
    

Log in to reply
 

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