> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/ix.-dynamic-programming/97.-interleaving-string.md).

# 97. Interleaving String

\# Hard 太难了

{% hint style="success" %}
How to define `interLeave[i][j]` is the key. Two-sequence DP problem. interLeave\[i]\[j] means `s1[:i]` and `s2[:j]` can completely match string of `s3[:i+j]`. bool value.

如何实现 `interLeave[i][j]`，如何做这道题，取决于如何定义`interLeave`这种有循环直奔结果的数组，并且正确的初始化第一个元素
{% endhint %}

### Solution:

1. Initilize `interLeave[len(s1)+1][len(s2)+1]`, `interLeave[i][0]` and `interLeave[0][j]`
2. Two cases can match:

   1. `s1[i] = s3[i+j]` and `interLeave[i-1][j]=True`
   2. `s2[j] = s3[i+j]` and `interLeave[i][j-1]=True`

   Then `interLeave[i][j] = True`

{% tabs %}
{% tab title="Python" %}

```python
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # edge case
        if len(s1)+len(s2) != len(s3):
            return False
        
        # interLeave[i][j] means if first i of s1 and j of s2 can be first (i+j) of s3 interleaving string
        # initialize interLeave
        interLeave = [[False]*(len(s2)+1) for i in range(len(s1)+1)]
        interLeave[0][0] = True
        for i in range(1, len(s1)+1):
            if s1[:i] == s3[:i]:
                interLeave[i][0] = True
        for j in range(1, len(s2)+1):
            if s2[:j] ==  s3[:j]:
                interLeave[0][j] = True
                
        # copmute
        for i in range(1, len(s1)+1):
            for j in range(1, len(s2)+1):
                if s1[i-1] == s3[i+j-1] and interLeave[i-1][j] == True:
                    interLeave[i][j] = True
                if s2[j-1] == s3[i+j-1] and interLeave[i][j-1] == True:
                    interLeave[i][j] = True

        return interLeave[len(s1)][len(s2)]
```

{% endtab %}

{% tab title="Java" %}

```java
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s3.length() != s1.length() + s2.length()) {
            return false;
        }
        
        boolean[][] match = new boolean[s1.length()+1][s2.length()+1];
        match[0][0] = true;
        for(int i = 1; i <= s1.length(); i ++)
            if(s1.charAt(i-1) == s3.charAt(i-1) && match[i-1][0])
                match[i][0] = true;
        
        for(int j = 1; j <= s2.length(); j ++)
            if(s2.charAt(j-1) == s3.charAt(j-1) && match[0][j-1])
                match[0][j] = true;
        
        for(int i = 1; i <= s1.length(); i ++)
            for(int j = 1; j <= s2.length(); j ++) {
                if(j == 0)
                    
                if((s3.charAt(i+j-1) == s1.charAt(i-1)) && match[i-1][j])
                    match[i][j] = true;
                if((s3.charAt(i+j-1) == s2.charAt(j-1)) && match[i][j-1])
                    match[i][j] = true;
            }
        return match[s1.length()][s2.length()];
    }
}
```

{% endtab %}
{% endtabs %}

{% hint style="danger" %}
Don't forget edge case, which can save a lot of time.
{% endhint %}