My DP solution in C++


  • 161
    S
     bool isInterleave(string s1, string s2, string s3) {
        
        if(s3.length() != s1.length() + s2.length())
            return false;
        
        bool table[s1.length()+1][s2.length()+1];
        
        for(int i=0; i<s1.length()+1; i++)
            for(int j=0; j< s2.length()+1; j++){
                if(i==0 && j==0)
                    table[i][j] = true;
                else if(i == 0)
                    table[i][j] = ( table[i][j-1] && s2[j-1] == s3[i+j-1]);
                else if(j == 0)
                    table[i][j] = ( table[i-1][j] && s1[i-1] == s3[i+j-1]);
                else
                    table[i][j] = (table[i-1][j] && s1[i-1] == s3[i+j-1] ) || (table[i][j-1] && s2[j-1] == s3[i+j-1] );
            }
            
        return table[s1.length()][s2.length()];
    }
    

    Here is some explanation:

    DP table represents if s3 is interleaving at (i+j)th position when s1 is at ith position, and s2 is at jth position. 0th position means empty string.

    So if both s1 and s2 is currently empty, s3 is empty too, and it is considered interleaving. If only s1 is empty, then if previous s2 position is interleaving and current s2 position char is equal to s3 current position char, it is considered interleaving. similar idea applies to when s2 is empty. when both s1 and s2 is not empty, then if we arrive i, j from i-1, j, then if i-1,j is already interleaving and i and current s3 position equal, it s interleaving. If we arrive i,j from i, j-1, then if i, j-1 is already interleaving and j and current s3 position equal. it is interleaving.


  • 1
    S

    Here is some explanation:

    DP table represents if s3 is interleaving at (i+j)th position when s1 is at ith position, and s2 is at jth position. 0th position means empty string.

    So if both s1 and s2 is currently empty, s3 is empty too, and it is considered interleaving. If only s1 is empty, then if previous s2 position is interleaving and current s2 position char is equal to s3 current position char, it is considered interleaving. similar idea applies to when s2 is empty. when both s1 and s2 is not empty, then if we arrive i, j from i-1, j, then if i-1,j is already interleaving and i and current s3 position equal, it s interleaving. If we arrive i,j from i, j-1, then if i, j-1 is already interleaving and j and current s3 position equal. it is interleaving.


  • 0
    S

    Thanks for updating, @sherryxmhe!
    I just updated your post with this comment.


  • 0
    H
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info.


  • 0
    X

    Great idea using DP!


  • 0
    M

    so neat! thanks for sharing


  • 0
    I

    Thanks, great idea!


  • 13
    P

    Very nice! For your easy understanding, in sherryxmhe's code, i and j can be treated as length of s1, s2 substrings. Further, the cache could be optimized to 1-D vector as below:

    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.length();
        int n = s2.length();
        int p = s3.length();
        
        if (m + n != p) return false;
        
        //initialize
        vector<bool> dp(n + 1);
        for (int j = 0; j <= n; j++)    dp[j] = s2.substr(0, j)==s3.substr(0, j); 
        
        for (int i = 1; i <= m; i++)
        {
            dp[0] = s1.substr(0, i)==s3.substr(0, i);
            for (int j = 1; j <= n; j++)
                dp[j] = (dp[j] && s3[i+j-1]==s1[i-1]) || (dp[j-1] && s3[i+j-1]==s2[j-1]);
        }
        
        return dp[n];
    
    }

  • 0
    This post is deleted!

  • 11

    Hi, sherryxmhe. Your code is really concise and elegant. Thanks for your sharing.

    I try to rewrite your code, also in C++, but find that it can only achieve 8ms, not the fastest. I guess handling 2d vector may be more time-consuming and thus optimize it to be of O(min(m, n)) space, but the running time does not change (still 8ms).

    Finally, I find that replacing vector<bool> dp(m, false); with bool* dp = new bool[m + 1](); reduces the running time to 0ms, which is just what I desire. Well, vector is really slow...

    The code is finally as follows (well, I do not release the allocated memory of dp, which is not desirable).

    class Solution { 
    public:
        bool isInterleave(string s1, string s2, string s3) {
            int m = s1.length(), n = s2.length(), l = s3.length();
            if (m > n) return isInterleave(s2, s1, s3);
            if (l != m + n) return false;
            bool *dp = new bool[m + 1]();
            dp[0] = true;
            for (int i = 1; i <= m; i++)
                dp[i] = dp[i - 1] && s3[i - 1] == s1[i - 1];
            for (int j = 1; j <= n; j++) {
                dp[0] = dp[0] && s3[j - 1] == s2[j - 1];
                for (int i = 1; i <= m; i++)
                    dp[i] = (dp[i - 1] && s3[i + j - 1] == s1[i - 1]) || (dp[i] && s3[i + j - 1] == s2[j - 1]);
            }
            return dp[m];
        }
    };

  • 0
    R

    Hi, jianchao.li.fighter! Can you explain how can can we use 1-D dp instead of 2-D? And how do you come up with the idea? Thank you!


  • 1

    Hi, rlaoyao. In fact, if a 2d-DP only depends on a single most recent state, then it can be simplified to a 1d-DP. The key to transforming a 2d-DP to a 1d-DP is that you should first write down the 2d-DP code and run it on some examples by drawing the 2d-table. After you become clear of the updating process of the table, you will have an idea of how to reduce the space to 1d. Well, it may be not that obvious at first. But you will gradually get it. Anyway, the key is to practice more :-)


  • 0
    R

    I have got it! Thanks!


  • 0

    Hi sherryxmhe, Thanks for your sharing. I rewrite your code in Java and made some modifications(init dp[i][0] and dp[0][i] in advance), and the code runs faster. :)

    public static boolean isInterleave(String s1, String s2, String s3) {
        int length1 = s1.length(), length2 = s2.length(), length3 = s3.length();
        if (length3 != length1 + length2)
            return false;
        boolean[][] dp = new boolean[length1 + 1][length2 + 1];
        for (int i = 0; i <= length1; i++)
            dp[i][0] = s1.substring(0, i).equals(s3.substring(0, i)) ? true : false;
        for (int i = 1; i <= length2; i++)
            dp[0][i] = s2.substring(0, i).equals(s3.substring(0, i)) ? true : false;
        for (int i = 1; i <= length1; i++) {
            for (int j = 1; j <= length2; j++) {
                dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }
        return dp[s1.length()][s2.length()];
    }

  • 0
    T

    A simple backtracking solution.

    bool isInterleave(const string &s1, const string &s2, const string &s3, int i, int j, int k, vector<vector<bool>> &visited){
            if (k == s3.size()) return true;
            if (visited[i][j]) return false;
            visited[i][j] = true;
            return i < s1.size() && s1[i] == s3[k] && isInterleave(s1, s2, s3, i + 1, j, k + 1, visited) || 
                   j < s2.size() && s2[j] == s3[k] && isInterleave(s1, s2, s3, i, j + 1, k + 1, visited);
        }
        
        bool isInterleave(string s1, string s2, string s3) {
            if (s1.size() + s2.size() != s3.size()) return false;
            vector<vector<bool> > visited(s1.size() + 1, vector<bool>(s2.size() + 1, false));
            return isInterleave(s1, s2, s3, 0, 0, 0, visited);
        }

  • 0
    T

    Wonderful idea! I just implement your idea with little modification of the code. jianchao.li.fighter already gave optimum solution with single dimension array. So, that will be the best. But, I feel comfortable to understand with 2-D array for this problem. Here is my solution:

    bool isInterleave(string s1, string s2, string s3) {
        int m= s1.size();
        int n = s2.size();
        int p = s3.size();
        if (p!=m+n) return false;
        vector<vector<bool>> dp(m+1,vector<bool>(n+1, false));
        dp[0][0] = true;
    
        for (int i = 1; i<=m;i++)
            dp[i][0] = dp[i-1][0] && s3[i-1] == s1[i-1];            
        for (int j = 1; j<=n;j++)
            dp[0][j] = dp[0][j-1] && s3[j-1] == s2[j-1];
    
        for (int i = 1; i<=m;i++)
            for (int j = 1; j<=n;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[m][n];        
    }

  • 0
    E

    Such a brilliant idea!!!
    May I ask why is this idea coms into your mind? My first thought is using backtracking to solve this problem, but I found it TLE...


  • 0
    P

    This is exactly with my thought, share my C++ code.

    bool isInterleave(string s1, string s2, string s3) {
        if (s3.size() != s1.size() + s2.size()) return false;
    
        int m = (int) s1.size();
        int n = (int) s2.size();
        // dp[i][j] = the first i chars in s1, the first j chars in s2
        // can or not can construct to the first (i+j) chars in s3
        vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
        // base case
        for (int len = 0; len <= n; ++len) {
            dp[0][len] = (s2.substr(0, len) == s3.substr(0, len));
        }
        for (int len = 0; len <= m; ++len) {
            dp[len][0] = (s1.substr(0, len) == s3.substr(0, len));
        }
    
        // bottom to up
        // the last char in s3[i+j-1] either comes from s1[i-1] or s2[j-1]
        // one of them lead to true, then the result is true
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = false;
                if (s1[i-1] == s3[i+j-1] && dp[i-1][j] == true) {
                    dp[i][j] = true;
                }
                if (s2[j-1] == s3[i+j-1] && dp[i][j-1] == true) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[m][n];
    }

  • 0
    N

    bool table[s1.length()+1][s2.length()+1]; Can I ask a c++ question?

    You can now indicate a array size with changing variable?


Log in to reply
 

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