# 97. Interleaving String

![](/files/GAgiAYHnWaVsAMGq9hGR)

time: O(m\*n), m is s1 length, n is s2 length

![](/files/nSABrT239f4vMfTEFRo0)

space: O(mn

```java
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        if (m+n != s3.length()) {
            return false;
        }
        
        boolean dp[][] = new boolean[m+1][n+1];
            
        s1 = "#" + s1;
        s2 = "#" + s2;
        s3 = "#" + s3;
        
        dp[0][0] = true; // all empty, s1+s2 == s3
        
        // 根據題意, 只要能交迭出 s3, 就是 true, 所以 s2 = "", 其實就是要要 s1 == s3
        // 所以從最後一位開始推是否相等
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i-1][0] && s1.charAt(i) == s3.charAt(i);
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j-1] && s2.charAt(j) == s3.charAt(j);
        }
        
        // 能交迭出, 就是s1 or s2 某字串的最後一位必定在 s3 最後一位
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (dp[i-1][j] && s1.charAt(i) == s3.charAt(i+j)) {
                    dp[i][j] = true;
                }
                if (dp[i][j-1] && s2.charAt(j) == s3.charAt(i+j)) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[m][n];
    }
}
```

## DFS + memo

#### 1 ms, faster than 99.10% of Java online submissions for Interleaving String.

T: O(mn)

S: O(mn)

```java
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        return dp(s1,s2,s3, 0, 0, new Boolean[s1.length()+1][s2.length()+1]);
    }
    private boolean dp(String s1, String s2, String s3, int i, int j, Boolean[][] memo) {
        int m = s1.length();
        int n = s2.length();
        int k = s3.length();
        if (i + j == k) {
            return true;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        boolean result = false;
        if (i < m && s3.charAt(i+j) == s1.charAt(i) && dp(s1,s2,s3,i+1, j, memo)) {
            result = true;
        }
        if (j < n && s3.charAt(i+j) == s2.charAt(j) && dp(s1,s2,s3,i, j+1, memo)) {
            result = true;
        }
        return memo[i][j] = result;
    }
    
}
```

#### or use ||, this one is easy to convert to 1D

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

## 1D

T: O(mn)

S: O(n)

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


/*
for (int i=1)
  for (int j = 1)
if (i > 0) {
    dp[i][j] = dp[i][j] || dp[i-1][j] && s1.charAt(i) == s3.charAt(i + j);
}
if (j > 0) {   
    dp[i][j] = dp[i][j] || dp[i][j-1] && s2.charAt(j) == s3.charAt(i + j);
}


      j1 
      0,1 0,2 0,3
i1        1,2

case1
if (i > 0) {  depends on J move => so same i, move j
dp[1][1] = dp[0][1] && ...
dp[1][2] = dp[0][2] && ...
if (i > 0) {
    dp[j] = dp[j] && s1.charAt(i) == s3.charAt(i + j);
}


case2
dp[1][1] = dp[1][0] &&...
dp[1][2] = dp[1][1] &&
if (j > 0) {  dp[j] depends dp[j-1]
    dp[j] = dp[j] || dp[j-1] && s2.charAt(j) == s3.charAt(i + j);
}
*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/pattern-matching-dp/97.-interleaving-string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.