[LeetCode] Interleaving String

Problem Statement (link):

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Analysis:
It reminds me of the Edit Distance problem. As we could break this problem down to some smaller problems, i.e., consider if s1[:i-1] and s2[:j-1] could build s[:i+j-1], we could use DP.

We could construct a matrix dp[s1.length()+1][s2.length()+1], remember in DP we usually leave one more extra space for initial condition, which is both s1 and s2 are blank string in this problem. Each entry dp[i][j] indicates whether s1[i-1] and s2[j-1] could build  s[:i+j-1].

Now consider the transfer function. dp[i][j] is true if either of the following cases is true:
1) current char in s1 is same as current char in s3, and previous dp entry in the same row is true
i.e., s1[i-1]==s3[i+j-1] && dp[i-1][j]) == true
2) current char in s2 is same as current char in s3, and previous dp entry in the same col is true
i.e., s2[j-1]==s3[i+j-1] && dp[i][j-1] == true

Our final answer is in the last entry of the DP matrix.

The time complexity of the algorithm is O(len1 * len2), where the two lengths are the lengths of s1 and s2, respectively.

Code:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int len1=s1.length(), len2=s2.length();
        if (len1+len2!=s3.length()) return false;
        vector<vector<bool>> dp(len1+1, vector<bool> (len2+1, false));

        // initial
        dp[0][0]=true;
        for (int i=1; i<=len1; i++)
            if (s1[i-1]==s3[i-1] && dp[i-1][0]) dp[i][0]=true;
        for (int j=1; j<=len2; j++)
            if (s2[j-1]==s3[j-1] && dp[0][j-1]) dp[0][j]=true;

        // update dp
        for (int i=1; i<=len1; i++) {
            for (int j=1; j<=len2; j++) {
                dp[i][j]=(s1[i-1]==s3[i+j-1] && dp[i-1][j]) || (s2[j-1]==s3[i+j-1] && dp[i][j-1]);
            }
        }
        return dp[len1][len2];
    }
};