A excellent solution but I cannot understand


  • -1
    L
    bool isInterleave(string s1, string s2, string s3) {
    if (s1.size() + s2.size() != s3.size())
        return false;
    if (s1.size() < s2.size())
        s1.swap(s2);
    vector<bool>  dp(s1.size() + 1);
    dp[0] = true;
    for (size_t j = 0; j <= s2.size(); ++j)
        for (size_t i = 1; i <= s1.size(); ++i)
            dp[i] = ((dp[i - 1] && s1[i - 1] == s3[i + j - 1])
                    || (j > 0 && dp[i] && s2[j - 1] == s3[i + j - 1]));
    return dp[s1.size()];
    

    }

    this code was found in the discussion before, but I got confused! I cannot understand why it need to swap s1 and s2 too get large size dp[]? acturally, the value in dp might be wrong, for example, when i = 0, j=2, the temprary result in dp always get dp[0] = ture, which means the usual dp method's dp[2][0] = true. this is incorrect, when using the transmitting function to get following result, the following result may also be incorrect. but why the final result is still correct?


  • 0
    S

    The original dp formula is

    dp[i][j] =  (dp[i - 1][j] AND s1[i - 1] = s3[i + j - 1])
                   OR (j > 0 AND dp[i][j-1] AND s2[j - 1] = s3[i + j - 1]))
    

    Look into this formula, dp[i][j] only counts on dp[i - 1][j] and dp[i][j - 1].

    The code in your post is using it.

     // To avoid confusion, I change i, j to u, v
     dp[v]   //  It is same as dp[i][j] . Pay attention, here is dp[v] instead of dp[u]
           = ((dp[v] && s1[u - 1] == s3[u + v - 1])      //   It is same as (dp[i - 1][j] AND s1[i - 1] = s3[i + j - 1]). Here the dp[v] is still dp[u - 1][v] indeed.
              || 
              (v > 0 && dp[v - 1] && s2[v - 1] == s3[u + v - 1]));  // It is same as (j > 0 AND dp[i][j-1] AND s2[j - 1] = s3[i + j - 1]))
    

    Above all, it can explain why the size of dp should always pick the larger one.


  • 0
    L

    Thank you for your reply. I understand the formula, and I know what you explained above except the final point: "Above all, it can explain why the size of dp should always pick the larger one." Why pick the larger one? What is wrong if I choose the smaller one?


  • 0
    L

    what confused me is : first, why choose the larger one as dp's dimension? second, why didn't calculate the dp[0]'s value at the beginning of the inner for loop? If dp[0] always true, I think this is wrong and would cause wrong answer, but this code got accepted by OJ, so, why is it right?


  • 0
    L

    I got the answer, this code is wrong, and the author means to get litter memory.


Log in to reply
 

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