###### tags: `Leetcode` `medium` `dynamic programming` `python`

# 97. Interleaving String

## [題目連結:] https://leetcode.com/problems/interleaving-string/

## 題目:
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 s and t are divided into n and m non-empty substrings respectively, 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```.

## 解題想法:
* 給三個string s1,s2,s3: 判斷s3是否可由s1,s2交錯組合而成
* s1、s2之原本組成之順序不能變
* 即s1 = 'abc',在使用時候,'a'一定要在'bc'前

* 使用dp:
* 定義dp[i][j]為:使用s1[:i]之string與s2[:j]之string，是否能交錯合併為s3[:i+j-1]
* 起始判斷:
* l1 = len(s1)
* l2 = len(s2)
* l3 = len(s3
* 若總長度l3!=l1+l2，return False
* init:
* dp = [[0 for _ in range(l2+1)] for _ in range(l1+1)]
* dp[0][0]=True
* s1不取任何字，s2不取任何字，能合成不取任何字的s3，所以為True
* 初始化第一行(左邊界)
* 意義為判斷s1中哪些位置的字元，對於在s3中相同位置，兩者字元相等
* 還需考慮上個位置使否為True，因為字元原本組成之順序不能變
* for i in range(1,l1+1):
dp[i][0] = dp[i-1][0] and (s1[i-1]==s3[i-1])
* 初始化第一列(上邊界)
* 意義為判斷s2中哪些位置的字元，對於在s3中相同位置，兩者字元相等
* 還需考慮上個位置使否為True，因為字元原本組成之順序不能變
* for j in range(1,l2+1):
dp[0][j] = dp[0][j-1] and (s2[j-1]==s3[j-1])
* 對於dp[i][j]:
* 考慮其 左方dp[i][j-1]與 上方dp[i-1][j]
* 若其中一者為True:
* if 左方s1為True:(dp[i][j-1]==True)
* 需再考慮 (其s2: 目前值s2[j-1]是否等於s3[i+j-1])
* if 上方s2為True:(dp[i-1][j]==True)
* 需再考慮 (其s1: 目前值s1[i-1]是否等於s3[i+j-1])
* 需判斷是否等於s3[i+j-1]原因為:因為總體長度須保持len(s1[:x])+len(s2[:y])=len(s3[:x+y-1])

* 示意dp數組

s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"

    s2  Ø   d   b   b   c   a
s1
Ø       T   F   F   F   F   F
a       T   F   F   F   F   F
a       T   T   T   T   T   F
b       F   T   T   F   T   F
c       F   F   T   T   T   T
c       F   F   F   T   F  'T' 
ans = True

## Python:

class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        #判斷
        l1 = len(s1)
        l2 = len(s2)
        l3 = len(s3)
        if (l1+l2)!=l3:
            return False
        #init
        dp = [[0 for _ in range(l2+1)] for _ in range(l1+1)]
        dp[0][0]=True
        #初始化上下邊
        for i in range(1,l1+1):
            dp[i][0] = dp[i-1][0] and (s1[i-1]==s3[i-1])
        #初始化左右邊
        for j in range(1,l2+1):
            dp[0][j] = dp[0][j-1] and (s2[j-1]==s3[j-1])
        #Dp
        for i in range(1,l1+1):
            for j in range(1,l2+1):
                dp[i][j] = (dp[i-1][j]==True and s1[i-1]==s3[i-1+j])or(dp[i][j-1]==True and s2[j-1]==s3[j-1+i])

        return dp[l1][l2]

result = Solution()
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"
ans = result.isInterleave(s1,s2,s3)
print(ans)