> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/interleaving-string.md).

# 97. Interleaving String

### Description

 Given *s1*, *s2*, *s3*, find whether *s3* is formed by the interleaving of *s1* and *s2*.

### Constraints

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/interleaving-string/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

**Output:** true
{% endtab %}

{% tab title="Example 2" %}
**Input:** s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"

**Output:** false
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(2^(m+n)). m is the length of s1 and n is the length of s2.
 * Space complexity : O(m+n). The size of stack for recursive calls 
 *    can go upto m+n.
 */

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if(m+n != s3.length()) return false;
        return helper(s1, m, 0, s2, n, 0, s3, "");
    }
    
    private boolean helper(String s1, int m, int i, 
                                       String s2, int n, int j, 
                                       String s3, 
                                       String s) {
        if(s3.equals(s) && i == m && j == n) {
            return true;
        }
        boolean ans = false;
        if(i < m) {
            ans |= helper(s1, m, i+1, s2, n, j, s3, s+s1.charAt(i));
        }
        if(j < n) {
            ans |= helper(s1, m, i, s2, n, j+1, s3, s+s2.charAt(j));
        }
        return ans;
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(m*n). dp array of size m*n is filled.
 * Space complexity : O(m*n). 2D dp of size (m+1)*(n+1) is required. m and n are 
 *    the lengths of strings s1 and s2 respectively.
 */

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length(), p = s3.length();
        if(m+n != p) return false;
        
        char[] s1Chars = s1.toCharArray();
        char[] s2Chars = s2.toCharArray();
        char[] s3Chars = s3.toCharArray();
        boolean[][] dp = new boolean[m+1][n+1];
        
        for(int i = 0; i <= m; i++) {
            for(int j = 0; j <= n; j++) {
                if(i == 0 && j == 0) {
                    dp[i][j] = true;
                } else if(i == 0) {
                    dp[i][j] = dp[i][j-1] && s2Chars[j-1] == s3Chars[i+j-1];
                } else if(j == 0) {
                    dp[i][j] = dp[i-1][j] && s1Chars[i-1] == s3Chars[i+j-1];
                } else {
                    dp[i][j] = (dp[i-1][j] && s1Chars[i-1] == s3Chars[i+j-1]) || 
                                (dp[i][j-1] && s2Chars[j-1] == s3Chars[i+j-1]);
                }
            }
        }
        
        return dp[m][n];
    }
}
```

{% endtab %}

{% tab title="Solution 3" %}

```java
/**
 * Time complexity : O(m*n). dp array of size n is filled m times.
 * Space complexity : O(n). n is the length of the string s1.
 */

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

{% endtab %}
{% endtabs %}

### **Follow up**

*