Interleaving String -- LeetCode

[Question]

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]
The straightforward way is to use recursion. Compare the first letter of s1, s2, s3,

1. If they are all different, the interleaving does not exist;
2. If s1[0] ==s3[0], s2[0]!= s3[0], the problem becomes if s3.substr(1, s3.end()) is an interleaving form of s1,substr(1, s1.end()) and s2; 
3. If s1[0]==s2[0]==s3[0], the code can explore two possibilities in sub-problems.

However it may make the computation complexity exponential.

Using Dynamic Programming, the computation can start from sub-problems, e.g. if the sub-strings of s1, s2, can be interleaved into sub-strings of s3. Like the problem of "Regular Expression Matching", this is 2D DP and can uses a 2D array to solve it.

Define M a matrix of (n+1) by (m+1), where n is size of s1 and m is the size of s2. M[i,j] is true, only when s1[0, i-1], s2[0, j-1] can be interleaved into s3[0.. i+j-1]. Populate M with the following rules:

1. M[i,j] = false         if s3[i+j-1] != s1[i-1] && s3[i+j-1]!=s2[j-1];
2. M[i,j]=M[i-1,j]      if s3[i+j-1] ==s1[i-1] && s1[i-1]!=s2[j-1];
3. M[i,j]=M[i,j-1]      if s3[i+j-1] ==s2[j-1] && s1[i-1]!=s2[j-1];
4. M[i,j]=M[i-1,j] || M[i,j-1]      if s3[i+j-1] ==s2[j-1] && s1[i-1]==s2[j-1];

In the end, M[n,m] is the answer. The time complexity is O(n * m).

[Solution]
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.empty()) return s2 == s3;
        if (s2.empty()) return s1 == s3;
        if (s3.size() != s1.size()+s2.size() ) return false;
     
        vector<vector<bool>> map(s1.size()+1, vector<bool>(s2.size()+1,false) );
        for (int i=1; i<s2.size()+1; i++)
            map[0][i] = s2[i-1] == s3[i-1];
        for (int i=1; i<s1.size()+1; i++)
            map[i][0] = s1[i-1] == s3[i-1];
     
        for (int i=1; i<s1.size()+1; i++)
            for (int j=1; j<s2.size()+1; j++) {
                char c3 = s3[i+j-1];
                char c2 = s2[j-1];
                char c1 = s1[i-1];
                if (c3!= c2 && c3!=c1) map[i][j] = false;
                else if (c3==c2 && c3==c1) map[i][j] = map[i-1][j] || map[i][j-1];
                else if (c3==c2) map[i][j] = map[i][j-1];
                else map[i][j] = map[i-1][j];
            }
        return map.back().back();
    }
};