# [LeetCode 97. Interleaving String ](https://leetcode.com/explore/challenge/card/june-leetcoding-challenge-2021/603/week-1-june-1st-june-7th/3765/)
### Daily challenge Jun 2, 2021 (MEDAIN)

>Given strings `s1`, `s2`, and `s3`, find whether s3 is formed by an **interleaving** of s1 and s2.
>
>An interleaving of two strings s and t is a configuration where they are divided into **non-empty** substrings such that:
>
>* s = s1 + s2 + ... + sn
>* t = t1 + t2 + ... + tm
>* |n - m| <= 1
>* The interleaving is `s1 + t1 + s2 + t2 + s3 + t3 + ...` or `t1 + s1 + t2 + s2 + t3 + s3 + ...`
>
>**Note:** a + b is the concatenation of strings a and b.


:::info
**Example 1:**
**Input:** s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
**Output:** true
:::

:::info
**Example 2:**
**Input:** s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
**Output:** false
:::

:::info
**Example 3:**
**Input:** s1 = "", s2 = "", s3 = ""
**Output:** true
:::

:::warning
**Constraints:**
* 0 <= s1.length, s2.length <= 100
* 0 <= s3.length <= 200
* s1, s2, and s3 consist of lowercase English letters.
:::

---

### Approach 1 : DP
**`0 ms ( 100% )`** **`O(n * m)`**

:::danger
假設三個字串的 `[0]` 皆表示 `NULL`。
**`DP[i][j]`** 代表 `s3[i+j-1]` 是否為 `Interleaving String` ，
when `s1` is at `[i-1]`, `s2` is at `[j-1]`。
:::


* **`s1[i-1] == s3[i+j-1]`**。
> 假設 `i, j = {3, 1}` ---> `s1[2] == s3[3]` `(b = b)`。
> 此時 `dp[2][1]` 若已經是 `Interleaving String` ，則 `dp[3][1]也是。`
* **`s2[j-1] == s3[i+j-1]`**
> 假設 `i, j = {2, 1}` ---> `s2[0] == s3[2]` `(d = d)`。
> 此時 `dp[2][0]` 若已經是 `Interleaving String` ，則 `dp[2][1]也是。`

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int len_s1 = s1.length();
        int len_s2 = s2.length();
        
        if(len_s1 + len_s2 != s3.length())    return false;
  
        bool dp[len_s1 + 1][len_s2 + 1];
        
        for(int i=0; i<=len_s1; i++){
            for(int j=0; j<=len_s2; j++){
                if(i == 0 && j ==0)    dp[i][j] = true;
                else if(i == 0)        dp[i][j] = (s2[j-1] == s3[i+j-1] && dp[i][j-1]);
                else if(j == 0)        dp[i][j] = (s1[i-1] == s3[i+j-1] && dp[i-1][j]);
                else                   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[len_s1][len_s2];
    }
};