Problem

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 they are divided into non-empty substrings 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.

To summarize: Interleaving of 2 strings is such that we break them into non-empty substring and concatenate them in the relative orders. For eg. s1=ABC, and s2=DEF, then when we split s1 in A, B, C, they should occur in same order in new string s3. Likewise for s2.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation:

s1: a  a              b  c     c
    ↓  ↓              ↓  ↓     ↓
s3: a  a  d  b  b  c  b  c  a  c
          ↑  ↑  ↑  ↑        ↑
s2:       d  b  b  c        a

Here is how we can make s3 from s1 and s2:

1. Take 'a' from s1 → "a"
2. Take 'a' from s1 → "aa" 
3. Take 'd' from s2 → "aad"
4. Take 'b' from s2 → "aadb"
5. Take 'b' from s2 → "aadbb"
6. Take 'c' from s1 → "aadbb" + "c" = "aadbbcc"
7. Take 'b' from s1 → "aadbbcb"
8. Take 'c' from s2 → "aadbbcbc"
9. Take 'a' from s2 → "aadbbcbca"
10. Take 'c' from s1 → "aadbbcbcac"

Result: s3 = "aadbbcbcac" ✓

Example 2:

1
2

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

Example 3:

1
2

Input: s1 = "", s2 = "", s3 = ""
Output: true

Solution

Method 1 - Brute Force

Intuition

Try every possible way to interleave s1 and s2 to form s3. At each step, choose either the next character from s1 or s2 if it matches the corresponding character in s3. Use backtracking to explore all possibilities.

Approach

Use recursion with three pointers (i1, i2, i3) for s1, s2, and s3. At each step, if the current character in s3 matches the next character in s1, recurse by advancing i1 and i3. Similarly, if it matches the next character in s2, recurse by advancing i2 and i3. If both match, try both options. If neither matches, backtrack.

Complexity

  • ⏰ Time complexity: O(2^(m+n)), where m and n are the lengths of s1 and s2. Each character can be chosen from either string, leading to exponential possibilities.
  • 🧺 Space complexity: O(m+n), due to the recursion stack depth.

Method 2 - Top Down DP with Memoization

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
	bool isInterleave(string s1, string s2, string s3) {
		int m = s1.size(), n = s2.size();
		if (m + n != s3.size()) return false;
		vector<vector<int>> memo(m + 1, vector<int>(n + 1, -1));
		function<bool(int, int)> dfs = [&](int i, int j) {
			if (i == m && j == n) return true;
			if (memo[i][j] != -1) return memo[i][j];
			int k = i + j;
			bool res = false;
			if (i < m && s1[i] == s3[k] && dfs(i + 1, j)) res = true;
			if (j < n && s2[j] == s3[k] && dfs(i, j + 1)) res = true;
			return memo[i][j] = res;
		};
		return dfs(0, 0);
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

func isInterleave(s1, s2, s3 string) bool {
	m, n := len(s1), len(s2)
	if m+n != len(s3) {
		return false
	}
	memo := make([][]int, m+1)
	for i := range memo {
		memo[i] = make([]int, n+1)
		for j := range memo[i] {
			memo[i][j] = -1
		}
	}
	var dfs func(i, j int) bool
	dfs = func(i, j int) bool {
		if i == m && j == n {
			return true
		}
		if memo[i][j] != -1 {
			return memo[i][j] == 1
		}
		k := i + j
		res := false
		if i < m && s1[i] == s3[k] && dfs(i+1, j) {
			res = true
		}
		if j < n && s2[j] == s3[k] && dfs(i, j+1) {
			res = true
		}
		if res {
			memo[i][j] = 1
		} else {
			memo[i][j] = 0
		}
		return res
	}
	return dfs(0, 0)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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[][] memo = new Boolean[m + 1][n + 1];
		return dfs(s1, s2, s3, 0, 0, memo);
	}
	private boolean dfs(String s1, String s2, String s3, int i, int j, Boolean[][] memo) {
		if (i == s1.length() && j == s2.length()) return true;
		if (memo[i][j] != null) return memo[i][j];
		int k = i + j;
		boolean res = false;
		if (i < s1.length() && s1.charAt(i) == s3.charAt(k) && dfs(s1, s2, s3, i + 1, j, memo)) res = true;
		if (j < s2.length() && s2.charAt(j) == s3.charAt(k) && dfs(s1, s2, s3, i, j + 1, memo)) res = true;
		return memo[i][j] = res;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
	fun isInterleave(s1: String, s2: String, s3: String): Boolean {
		val m = s1.length
		val n = s2.length
		if (m + n != s3.length) return false
		val memo = Array(m + 1) { Array<Boolean?>(n + 1) { null } }
		fun dfs(i: Int, j: Int): Boolean {
			if (i == m && j == n) return true
			memo[i][j]?.let { return it }
			val k = i + j
			var res = false
			if (i < m && s1[i] == s3[k] && dfs(i + 1, j)) res = true
			if (j < n && s2[j] == s3[k] && dfs(i, j + 1)) res = true
			memo[i][j] = res
			return res
		}
		return dfs(0, 0)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
	def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
		m, n = len(s1), len(s2)
		if m + n != len(s3):
			return False
		memo = {}
		def dfs(i, j):
			if (i, j) in memo:
				return memo[(i, j)]
			if i == m and j == n:
				return True
			k = i + j
			res = False
			if i < m and s1[i] == s3[k] and dfs(i + 1, j):
				res = True
			if j < n and s2[j] == s3[k] and dfs(i, j + 1):
				res = True
			memo[(i, j)] = res
			return res
		return dfs(0, 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
	pub fn is_interleave(s1: String, s2: String, s3: String) -> bool {
		let m = s1.len();
		let n = s2.len();
		if m + n != s3.len() { return false; }
		let s1 = s1.as_bytes();
		let s2 = s2.as_bytes();
		let s3 = s3.as_bytes();
		let mut memo = vec![vec![None; n + 1]; m + 1];
		fn dfs(i: usize, j: usize, s1: &[u8], s2: &[u8], s3: &[u8], memo: &mut Vec<Vec<Option<bool>>>) -> bool {
			if let Some(v) = memo[i][j] { return v; }
			if i == s1.len() && j == s2.len() { return true; }
			let k = i + j;
			let mut res = false;
			if i < s1.len() && s1[i] == s3[k] && dfs(i + 1, j, s1, s2, s3, memo) { res = true; }
			if j < s2.len() && s2[j] == s3[k] && dfs(i, j + 1, s1, s2, s3, memo) { res = true; }
			memo[i][j] = Some(res);
			res
		}
		dfs(0, 0, s1, s2, s3, &mut memo)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

function isInterleave(s1: string, s2: string, s3: string): boolean {
	const m = s1.length, n = s2.length;
	if (m + n !== s3.length) return false;
	const memo: (boolean | undefined)[][] = Array.from({ length: m + 1 }, () => Array(n + 1));
	function dfs(i: number, j: number): boolean {
		if (memo[i][j] !== undefined) return memo[i][j]!;
		if (i === m && j === n) return true;
		const k = i + j;
		let res = false;
		if (i < m && s1[i] === s3[k] && dfs(i + 1, j)) res = true;
		if (j < n && s2[j] === s3[k] && dfs(i, j + 1)) res = true;
		memo[i][j] = res;
		return res;
	}
	return dfs(0, 0);
}

Method 3 - Bottom up DP

Intuition

Use dynamic programming to build a table dp[i][j] indicating whether s3[0..i+j-1] can be formed by interleaving s1[0..i-1] and s2[0..j-1]. Start from the base case and fill the table iteratively.

Approach

Create a 2D DP table of size (m+1) x (n+1). Initialize dp[0][0] = True. For each cell, check if the previous state is valid and the current character matches. Fill the table row by row and return dp[m][n].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
	bool isInterleave(string s1, string s2, string s3) {
		int m = s1.size(), n = s2.size();
		if (m + n != s3.size()) return false;
		vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
		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[i-1] == s3[i+j-1]);
				if (j > 0)
					dp[i][j] = dp[i][j] || (dp[i][j-1] && s2[j-1] == s3[i+j-1]);
			}
		}
		return dp[m][n];
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func isInterleave(s1, s2, s3 string) bool {
	m, n := len(s1), len(s2)
	if m+n != len(s3) {
		return false
	}
	dp := make([][]bool, m+1)
	for i := range dp {
		dp[i] = make([]bool, n+1)
	}
	dp[0][0] = true
	for i := 0; i <= m; i++ {
		for j := 0; j <= n; j++ {
			if i > 0 && dp[i-1][j] && s1[i-1] == s3[i+j-1] {
				dp[i][j] = true
			}
			if j > 0 && dp[i][j-1] && s2[j-1] == s3[i+j-1] {
				dp[i][j] = true
			}
		}
	}
	return dp[m][n]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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[m + 1][n + 1];
		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-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1);
				if (j > 0)
					dp[i][j] |= dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1);
			}
		}
		return dp[m][n];
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
	fun isInterleave(s1: String, s2: String, s3: String): Boolean {
		val m = s1.length
		val n = s2.length
		if (m + n != s3.length) return false
		val dp = Array(m + 1) { BooleanArray(n + 1) }
		dp[0][0] = true
		for (i in 0..m) {
			for (j in 0..n) {
				if (i > 0)
					dp[i][j] = dp[i][j] || (dp[i-1][j] && s1[i-1] == s3[i+j-1])
				if (j > 0)
					dp[i][j] = dp[i][j] || (dp[i][j-1] && s2[j-1] == s3[i+j-1])
			}
		}
		return dp[m][n]
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
	def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
		m, n = len(s1), len(s2)
		if m + n != len(s3):
			return False
		dp = [[False] * (n + 1) for _ in range(m + 1)]
		dp[0][0] = True
		for i in range(m + 1):
			for j in range(n + 1):
				if i > 0:
					dp[i][j] |= dp[i-1][j] and s1[i-1] == s3[i+j-1]
				if j > 0:
					dp[i][j] |= dp[i][j-1] and s2[j-1] == s3[i+j-1]
		return dp[m][n]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
	pub fn is_interleave(s1: String, s2: String, s3: String) -> bool {
		let m = s1.len();
		let n = s2.len();
		if m + n != s3.len() { return false; }
		let s1 = s1.as_bytes();
		let s2 = s2.as_bytes();
		let s3 = s3.as_bytes();
		let mut dp = vec![vec![false; n + 1]; m + 1];
		dp[0][0] = true;
		for i in 0..=m {
			for j in 0..=n {
				if i > 0 && dp[i-1][j] && s1[i-1] == s3[i+j-1] {
					dp[i][j] = true;
				}
				if j > 0 && dp[i][j-1] && s2[j-1] == s3[i+j-1] {
					dp[i][j] = true;
				}
			}
		}
		dp[m][n]
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

function isInterleave(s1: string, s2: string, s3: string): boolean {
	const m = s1.length, n = s2.length;
	if (m + n !== s3.length) return false;
	const dp: boolean[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));
	dp[0][0] = true;
	for (let i = 0; i <= m; i++) {
		for (let j = 0; j <= n; j++) {
			if (i > 0 && dp[i-1][j] && s1[i-1] === s3[i+j-1]) {
				dp[i][j] = true;
			}
			if (j > 0 && dp[i][j-1] && s2[j-1] === s3[i+j-1]) {
				dp[i][j] = true;
			}
		}
	}
	return dp[m][n];
}

Complexity

  • ⏰ Time complexity: O(mn), where m and n are the lengths of s1 and s2. Each cell in the DP table is computed once.
  • 🧺 Space complexity: O(mn), for the DP table.