Sharing my 12ms C++ solution using DP


  • 0
    T
    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            int n1 = s1.length();
            int n2 = s2.length();
            int n3 = s3.length();
            if(n1+n2 != n3)
                return false;
                
            vector<vector<bool>> DP;
            DP.resize(n1+1);
            int i, j;
            for(i=0; i<=n1; i++)
                DP[i].resize(n2+1, false);
                
            DP[0][0] = true;
            for(j=1; j<=n2; j++)
                DP[0][j] = (DP[0][j-1] && s2[j-1] == s3[j-1]);
            for(i=1; i<=n1; i++)
                DP[i][0] = (DP[i-1][0] && s1[i-1] == s3[i-1]);
            for(i=1; i<=n1; i++)
                for(j=1; j<=n2; j++)
                {
                    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]);
                }
                
            return DP[n1][n2];
        }
    };

Log in to reply
 

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