97. Interleaving String

dp[i][j] represents that s3 is interleaving at position i+j when s1 is at position i and s2 is at position j. Note, 0th position is the empty string.

Then, if we want to know if s3 is interleaving at position i+j, we have two cases to deal with:

Case 1: s3 is interleaving at position i-1+j when s1 is at position i-1 and s2 is at position j, i.e. dp[i-1][j] == true. So if s3 is interleaving at position i+j, then, character at position i in s1 must equal to character at position i+j in s3. Considering 0the position is the empty string here, ith position is actually i-1 in s1. Therefore, dp[i][j] = dp[i-1][j] && s1[i-1] == s3[i-1+j]

Case 2: s3 is interleaving at position i+j-1 when s1 is at position i and s2 is at position j-1. Similar to case 1, dp[i][j] = dp[i][j-1] && s2[j-1] == s3[i+j-1]

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