Regular DP solution C++


  • 0
    X
    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            if (s1.length() + s2.length() != s3.length()) return false;
            if (s1.length() == 0) return s2 == s3;
            if (s2.length() == 0) return s1 == s3;
            int m = s1.length();
            int n = s2.length();
            vector<vector<bool> > dp(m + 1, vector<bool>(n + 1, false));
            //dp[i][j] indicates that whether s1[0....i-1] s2[0......j-1] interleaves s3[0......i+j-1]
            //to calculate dp[i][j]
            //consider two case:
            //if dp[i-1][j] = true; s1[i-1] == s3[i+j-1], then dp[i][j] = true
            //if dp[i][j-1] = true; s2[j-1] == s3[i+j-1], then dp[i][j] = true
            dp[0][0] = true;
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    //first consider dp[i-1][j]
                    if (i > 0 && dp[i-1][j] && s1[i-1] == s3[i+j-1]) {
                            dp[i][j] = true; continue;
                    }
                    //next consider dp[i][j-1]
                    if (j > 0 && dp[i][j-1] && s2[j-1] == s3[i+j-1]) {
                            dp[i][j] = true;
                    }
                }
            }
            return dp[m][n];
        }
    };

Log in to reply
 

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