0ms C++ Classical DP Solution


  • 1
    Y
    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            int p = s1.size(), q = s2.size(), r = s3.size();
            if (p+q != r) return false;
            bool dp[p+1][q+1];
            dp[0][0] = true;
            for (int i = 1; i <= p; i++) dp[i][0] = (dp[i-1][0] && s1[i-1] == s3[i-1]);
            for (int i = 1; i <= q; i++) dp[0][i] = (dp[0][i-1] && s2[i-1] == s3[i-1]);
            for (int i = 1; i <= p; i++) {
                for (int j = 1; j <= q; j++) {
                    if (dp[i-1][j] && s1[i-1] == s3[i+j-1]) dp[i][j] = true;
                    else if (dp[i][j-1] && s2[j-1] == s3[i+j-1]) dp[i][j] = true;
                    else dp[i][j] = false;
                }
            }
            return dp[p][q];
        }
    };
    

    Bottom up DP approach. dp[ i ][ j ] represents whether prefix of s3 of length i+j is an interleaving string of prefix of s1 of length i and prefix of s2 of length j.


Log in to reply
 

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