97. Interleaving String
給你三個字串 s1,s2,s3 ，求出是否可以透過交替的插入s1和s2的字元來得到s3。
Example 1:
https://assets.leetcode.com/uploads/2020/09/02/interleave.jpg
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" =
"aadbbcbcac".
Since s3 can be obtained by interleaving s1 and s2, we return true.
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Explanation: Notice how it is impossible to interleave s2 with any other
string to obtain s3.
Example 3:
Input: s1 = "", s2 = "", s3 = ""
Output: true
思路：
1.選或不選大多都是動態規劃問題，先找幾個簡單的case畫一張表格就可以看出
遞移的方程式了。
2.首先排除明顯不符合的 case，若 s1 和 s2 相加長度不等於 s3 可以直接返回 false。
3.定義dp[i][j] 表示用了 i 個 s1 字元、j 個 s2 的字元組出來的字串是否等於
s3[0,i+j]，要得到當前的 dp[i][j] 只可能有兩種方式組合：
> 用了 i-1 個 s1，j 個 s1 字元，並使用了第 i 個 s1 字元
> 用了 i 個 s1，j -1 個 s2 字元，並使用了第 j 個 s2 字元
如果前一輪組的字串等於 s3 的子字串且當前拿的字串也等於 s3 的下個字串當前就為
true，只要其中一種拿法為真即可（ab 和 ba 不重要）。
4.因為要取前一個所以要初始化第一行和第一列，base case dp[0][0] 為 true，跑完
動態規劃返回 dp[n][m] 即可。
Java Code：