My C++ DP solution


  • 4
    D

    This is a typical DP problem. Use an array to save the intermediate matching result. dp[i][j] represents if s3[0::i+j-1] is an interleaved version of s1[0::i-1] and s2[0::j-1]. The recursive equation is dp[i][j] = ( dp[i-1][j] && (s1[i-1]==s3[i+j-1]) ) || ( dp[i][j-1] && (s2[j-1]==s3[i+j-1]) ). This equation only needs dp[i][] and dp[i-1][], so two rows are enough.

    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            int len1 = s1.size(), len2 = s2.size(), len3 = s3.size(), row, col;
            if(len1+len2!=len3) return false;//if the length doesn't match
            if(!len1 || !len2) return s3 == s1+s2; // if at least one (s1 or s2) is empty, compare if the other equals to s3
            bool dp[2][len2+1];
    
            for(col=1, dp[0][0] = true; col<=len2;++col)
                dp[0][col] = dp[0][col-1] && (s2[col-1] == s3[col-1]); // generate the first row of dp
            
            for(row=1; row<=len1;++row)
                for(col=1, dp[row%2][0] = dp[(row-1)%2][0] && (s1[row-1]==s3[row-1]) ; col<=len2;++col)
                    dp[row%2][col] = (dp[row%2][col-1] && s2[col-1] == s3[row+col-1]) ||
                                     (dp[(row-1)%2][col] && s1[row-1] == s3[row+col-1]); // recursive equation
            return dp[len1%2][len2];                         
         }
    };

  • 0

    Here is my C version of the same solution, it works nice! Thanks for sharing!

    //AC - 0ms - DP solution;
    bool isInterleave(char* s1, char* s2, char* s3)
    {
        int len1=strlen(s1), len2=strlen(s2);
        if(!len1 || !len2) return !strcmp(s1, s3) || !strcmp(s2, s3);
        if(strlen(s3) != len1+len2) return false;
        bool* cur=(bool*)malloc(sizeof(bool)*(len2+1));
        bool* pre=(bool*)malloc(sizeof(bool)*(len2+1));
        memset(pre, 0, sizeof(bool)*(len2+1));
        pre[0] = true; //initialize boundary condition;
        for(int i = 1; i <= len2; i++)
            if(s2[i-1] == s3[i-1])
                pre[i] = true;
            else
                break;
        for(int i = 1; i <= len1; i++) //i and j represent length of s1 and s2 respectively;
        {
            for(int j = 0; j <= len2; j++)
                cur[j] = (j>0 && cur[j-1] && s2[j-1]==s3[i+j-1]) ||
                    (pre[j] && s1[i-1]==s3[i+j-1]);
            bool *t = pre; pre = cur; cur = t;
        }
        return pre[len2];
    }
    

Log in to reply
 

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