Notes:

1. Even s3 is empty string, if s1 and s2 are emtpy, then it should be true.

2. Do not mess up the size of label.

1 class Solution { 2 public: 3     bool isInterleave(string s1, string s2, string s3) { 4         int l1 = s1.size(), l2 = s2.size(), l3 = s3.size(); 5         if (l3 != l2 + l1) return false; 6         vector
     
      
        > dp(l1+1, vector
       
         (l2+1, false)); 7         dp[0][0] = true; 8         for (int i = 1; i <= l1; i++) dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1]; 9         for (int i = 1; i <= l2; i++) dp[0][i] = dp[0][i-1] && s2[i-1] == s3[i-1];10         for (int i = 1; i <= l1; i++) {11             for (int j = 1; j <= l2; j++) {12                 dp[i][j] = ((dp[i-1][j] && s1[i-1] == s3[i+j-1]) ||13                             (dp[i][j-1] && s2[j-1] == s3[i+j-1]) ||14                             (dp[i-1][j-1] && s1[i-1] == s3[i+j-1] && s2[j-1] == s3[i+j-2]) ||15                             (dp[i-1][j-1] && s1[i-1] == s3[i+j-2] && s2[j-1] == s3[i+j-1]));16             }17         }18         return dp[l1][l2];19     }20 };