---
# System prepended metadata

title: 97. Interleaving String
tags: [Leetcode, medium, python, dynamic programming]

---

###### 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:
``` 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)
```