LC097 - Interleaving String

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 s and t are divided into n and m 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.

Example

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

Output: true

Explanation: One way to obtain s3 is: Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a". Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac". Since s3 can be obtained by interleaving s1 and s2, we return true.

Solution

Cached DFS

We find whether or not it is possible to merge s1 and s2 into s3, with the substrings in original order. We use three pointers, one on each string, incrementing when a match is found between s1/s2 and s3, alternating between s1 and s2 when a match is not found. When it is possible to increment the pointer at both s1 and s2, there exists a branch in the decision tree, and we must then backtrack. Caching is used to reduce the effective depth of the tree from $O(2^n)$ to $O(m\cdot n)$, at the cost of extra space used for the cache.

def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
	@cache
	def dfs(i, j):
		if i == len(s1) and j == len(s2):
			return True
		if i < len(s1) and s1[i] == s3[i+j] and dfs(i+1, j):
			return True
		if j < len(s2) and s2[j] == s3[i+j] and dfs(i, j+1):
			return True
		return False
	

	if len(s1) + len(s2) != len(s3):
		return False
	else:
		return dfs(0,0)

2D Dynamic Programming

The 2D dynamic programming approach takes about the same time and memory as the cached DFS approach.

def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
	if len(s1) + len(s2) != len(s3):
		return False
		
	arr = [[False for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
	arr[len(s1)][len(s2)] = True

	for i in range(len(s1), -1, -1):
		for j in range(len(s2), -1, -1):
			if i < len(s1) and s1[i] == s3[i+j] and arr[i+1][j]:
				arr[i][j] = True
			if j < len(s2) and s2[j] == s3[i+j] and arr[i][j+1]:
				arr[i][j] = True
	return arr[0][0]