C++ Straightforward DP Solution


  • 0

    We can use a 2D vector of boolean values to represent whether a substring a s3 can be composed by substring of s1 and s2. The recurrence relation is:

    dp[i][j] = ture if

    • s1[i-1] == s3[i+j-1] and dp[i-1][j]. Which means we want to use character s1[i-1] to compose s3[i+j-1]
    • or s2[j-1] == s3[i+j-1] and dp[i][j-1]. Which means we want to use character s2[j-1] to compose s3[i+j-1]
    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            int size1 = s1.size();
            int size2 = s2.size();
            int size3 = s3.size();
            if(size1 + size2 != size3) return false;
            
            vector<vector<bool>> dp(size1 + 1, vector<bool>(size2 + 1, false));
            dp[0][0] = true;
            
            for(int i = 0; i <= size1; ++i){
                for(int j = 0; j <= size2; ++j){
                    if(i > 0 && s1[i-1] == s3[i+j-1] && dp[i-1][j]){
                        dp[i][j] = true;
                    }else if(j > 0 && s2[j-1] == s3[i+j-1] && dp[i][j-1]){
                        dp[i][j] = true;
                    }
                }
            }
            
            return dp[size1][size2];
        }
    };
    

Log in to reply
 

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