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

Example 1:


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


Example 2:


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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Starter code: class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        

Solutions:
class Solution:

	def isInterleave(self, s1, s2, s3):
		if len(s3) != len(s1) + len(s2):
			return False
		if not s1 or not s2:
			return (s1 or s2) == s3
		options = {(0, 0)}
		for char in s3:
			new_options = set()
			for (i1, i2) in options:
				if i1 < len(s1) and char == s1[i1]:
					new_options.add((i1 + 1, i2))
				if i2 < len(s2) and char == s2[i2]:
					new_options.add((i1, i2 + 1))
			options = new_options
			if not options:
				return False
		return True


class Solution:

	def isInterleave(self, s1, s2, s3):
		if len(s1) + len(s2) != len(s3):
			return False
		(l1, l2, l3) = (len(s1) + 1, len(s2) + 1, len(s3) + 1)
		dp = [True for i in range(l2)]
		for i in range(1, l2):
			dp[i] = dp[i - 1] and s2[i - 1] == s3[i - 1]
		for i in range(1, l1):
			dp[0] = dp[0] and s1[i - 1] == s3[i - 1]
			for j in range(1, l2):
				dp[j] = dp[j] and s1[i - 1] == s3[i + j - 1] or (dp[j - 1] and s2[j - 1] == s3[i + j - 1])
		return dp[-1]


class Solution:

	def isInterleave(self, s1, s2, s3):
		if len(s1) + len(s2) != len(s3):
			return False
		if not s1 and s2 and s3:
			return True if s2 == s3 else False
		if not s2 and s1 and s3:
			return True if s1 == s3 else False
		if not s1 and (not s2) and (not s3):
			return True
		if s1 and s2 and (not s3) or (not s1 and (not s2) and s3):
			return False
		result = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
		result[0][0] = True
		for i in range(len(s1) + 1):
			il_idx = i - 1
			for j in range(len(s2) + 1):
				if i == j == 0:
					continue
				if j > len(s3) - 1:
					break
				(s1_idx, s2_idx) = (i - 1, j - 1)
				s1_char = s1[s1_idx] if s1_idx > -1 else None
				s2_char = s2[s2_idx] if s2_idx > -1 else None
				il_char = s3[il_idx + j]
				top = False if i == 0 else result[i - 1][j]
				left = False if j == 0 else result[i][j - 1]
				ds = set()
				if not left:
					ds.add(s1_char)
				if not top:
					ds.add(s2_char)
				result[i][j] = il_char in ds and (top or left)
				if s1_char == s2_char == il_char and top and left:
					result[i][j] = True
		return result[-1][-1]


class Solution:

	def isInterleave(self, s1, s2, s3):
		if len(s1) + len(s2) != len(s3):
			return False
		(m, n) = (len(s1) + 1, len(s2) + 1)
		dp = [[False] * n for _ in range(m)]
		dp[0][0] = True
		for row in range(1, m):
			dp[row][0] = dp[row - 1][0] and s1[row - 1] == s3[row - 1]
		for col in range(1, n):
			dp[0][col] = dp[0][col - 1] and s2[col - 1] == s3[col - 1]
		for row in range(1, m):
			for col in range(1, n):
				dp[row][col] = dp[row - 1][col] and s1[row - 1] == s3[row + col - 1] or (dp[row][col - 1] and s2[col - 1] == s3[row + col - 1])
		return dp[-1][-1]


class Solution:

	def isInterleave(self, s1, s2, s3):
		(l1, l2) = (len(s1), len(s2))
		if len(s3) != l1 + l2:
			return False
		if l1 == 0 or l2 == 0:
			return l1 and s1 == s3 or (l2 and s2 == s3) or (not s3)
		dp = [[False] * (l2 + 1) for _ in range(l1 + 1)]
		dp[0][0] = True
		for i in range(l1):
			if s1[i] == s3[i]:
				dp[i + 1][0] = True
			else:
				break
		for i in range(l2):
			if s2[i] == s3[i]:
				dp[0][i + 1] = True
			else:
				break
		for i in range(1, l1 + 1):
			for j in range(1, l2 + 1):
				dp[i][j] = s1[i - 1] == s3[i + j - 1] and dp[i - 1][j] or (s2[j - 1] == s3[i + j - 1] and dp[i][j - 1])
		return dp[-1][-1]


class Solution:

	def isInterleave(self, s1, s2, s3):
		if len(s3) != len(s1) + len(s2):
			return False
		if '' in [s1, s2]:
			return s3 == s1 + s2
		dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
		for i in range(len(s1) + 1):
			for j in range(len(s2) + 1):
				if i == 0 and j == 0:
					dp[i][j] = True
				else:
					dp[i][j] = False
					if j > 0:
						dp[i][j] |= dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]
					if i > 0:
						dp[i][j] |= dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]
		return dp[-1][-1]


class Solution:

	def bruteForce(self, s1, s2, s3, i, j, k, string, m):
		try:
			return m[i, j]
		except KeyError:
			if k >= len(s3):
				if string == s3:
					m[i, j] = True
					return True
				else:
					m[i, j] = False
					return False
			else:
				x = False
				y = False
				xstring = string[:]
				if i < len(s1):
					if s1[i] == s3[k]:
						if not string:
							string = s1[i]
						else:
							string = string + s1[i]
						x = self.bruteForce(s1, s2, s3, i + 1, j, k + 1, string, m)
						if x == True:
							m[i, j] = True
							return True
				if j < len(s2):
					if s2[j] == s3[k]:
						if not xstring:
							xstring = s2[j]
						else:
							xstring = xstring + s2[j]
						y = self.bruteForce(s1, s2, s3, i, j + 1, k + 1, xstring, m)
				m[i, j] = x or y
				return x or y

	def isInterleave(self, s1, s2, s3):
		if not s1 and (not s2) and (not s3):
			return True
		if not s1:
			if s2 == s3:
				return True
			else:
				return False
		if not s2:
			if s1 == s3:
				return True
			else:
				return False
		if len(s3) != len(s1) + len(s2):
			return False
		return self.bruteForce(s1, s2, s3, 0, 0, 0, '', {})


class Solution:

	def isInterleave(self, s1, s2, s3):
		if s1 == '' and s2 == '' and (s3 == ''):
			return True
		if len(s1) + len(s2) != len(s3):
			return False
		paths = [[False for i in range(len(s1) + 1)] for j in range(len(s2) + 1)]
		for i in range(1, len(s1) + 1):
			if s1[i - 1] == s3[i - 1]:
				paths[0][i] = True
			else:
				break
		for i in range(1, len(s2) + 1):
			if s2[i - 1] == s3[i - 1]:
				paths[i][0] = True
			else:
				break
		for i in range(1, len(s2) + 1):
			for j in range(1, len(s1) + 1):
				if paths[i][j - 1] is True and s1[j - 1] == s3[i + j - 1] or (paths[i - 1][j] is True and s2[i - 1] == s3[i + j - 1]):
					paths[i][j] = True
		return paths[len(s2)][len(s1)]


class Solution:

	def qute_print(self, A):
		for row in A:
			for elem in row:
				print('{:2}'.format(elem), end=' ')
			print()

	def isInterleave(self, A, B, C):
		(n, m) = (len(A), len(B))
		if len(C) != n + m:
			return False
		dp = [[False] * (m + 1) for _ in range(n + 1)]
		dp[0][0] = True
		for i in range(1, n + 1):
			dp[i][0] = bool(dp[i - 1][0] * (A[i - 1] == C[i - 1]))
		for j in range(1, m + 1):
			dp[0][j] = bool(dp[0][j - 1] * (B[j - 1] == C[j - 1]))
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if A[i - 1] == C[i + j - 1]:
					dp[i][j] = dp[i - 1][j]
				if not dp[i][j] and B[j - 1] == C[i + j - 1]:
					dp[i][j] = dp[i][j - 1]
		return dp[-1][-1]


class Solution:

	def isInterleave(self, s1, s2, s3):
		if len(s1) + len(s2) != len(s3):
			return False
		res = [[False for j in range(1 + len(s2))] for i in range(1 + len(s1))]
		for i in range(1 + len(s1)):
			for j in range(1 + len(s2)):
				if i == 0 and j == 0:
					res[i][j] = True
				elif i == 0:
					res[i][j] = res[i][j - 1] and s3[i + j - 1] == s2[j - 1]
				elif j == 0:
					res[i][j] = res[i - 1][j] and s3[i + j - 1] == s1[i - 1]
				else:
					res[i][j] = res[i][j] or (s3[i + j - 1] == s1[i - 1] and res[i - 1][j])
					res[i][j] = res[i][j] or (s3[i + j - 1] == s2[j - 1] and res[i][j - 1])
		return res[len(s1)][len(s2)]