Given strings A, B, and C, find whether C is formed by an interleaving of A and B.
An interleaving of two strings S and T is a configuration such that it creates a new string Y from the concatenation substrings of A and B and |Y| = |A + B| = |C|
For example:
A = "XYZ"
B = "ABC"
so we can make multiple interleaving string Y like, XYZABC, XAYBCZ, AXBYZC, XYAZBC and many more so here your task is to check whether you can create a string Y which can be equal to C.
Specifically, you just need to create substrings of string A and create substrings B and concatenate them and check whether it is equal to C or not.
Note: a + b is the concatenation of strings a and b.
Return true if C is formed by an interleaving of A and B, else return false.
Example 1:
Input:
A = YX, B = X, C = XXY
Output: 0
Explanation: XXY is not interleaving
of YX and X
Example 2:
Input:
A = XY, B = X, C = XXY
Output: 1
Explanation: XXY is interleaving of
XY and X.
Your Task:
Complete the function isInterleave() which takes three strings A, B and C as input and returns true if C is an interleaving of A and B else returns false. (1 is printed by the driver code if the returned value is true, otherwise 0.)
Expected Time Complexity: O(N * M)
Expected Auxiliary Space: O(N * M)
here, N = length of A, and M = length of B
Constraints:
1 ≤ length of A, B ≤ 100
1 ≤ length of C ≤ 200

Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures
Expected Time Complexity: O(N * M)
Expected Auxiliary Space: O(N * M)

Starter code:
#User function Template for python3



 #Your task is to complete this Function \



class Solution:

    #function should return True/False

    def isInterleave(self, A, B, C):

        # Code here

Solutions:
class Solution:

	def solve(self, i, j, k, a, b, c, dp):
		if i == len(a) and j == len(b) and (k == len(c)):
			return 1
		if dp[i][j] != -1:
			return dp[i][j]
		(ans1, ans2) = (0, 0)
		if i < len(a) and a[i] == c[k]:
			ans1 = self.solve(i + 1, j, k + 1, a, b, c, dp)
		if j < len(b) and b[j] == c[k]:
			ans2 = self.solve(i, j + 1, k + 1, a, b, c, dp)
		dp[i][j] = ans1 + ans2
		return dp[i][j]

	def isInterleave(self, A, B, C):
		j = 0
		i = 0
		k = 0
		dp = [[-1 for i in range(len(B) + 1)] for j in range(len(A) + 1)]
		if len(A) + len(B) != len(C):
			return 0
		return self.solve(i, j, k, A, B, C, dp)


class Solution:

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


import numpy as np

class Solution:

	def rec_sol(self, A, B, C, i, j, k, dp):
		if i == 0 and j == 0:
			return True
		temp = False
		if dp[i][j][k] != None:
			return dp[i][j][k]
		if i > 0 and A[i - 1] == C[k - 1]:
			temp = temp or self.rec_sol(A, B, C, i - 1, j, k - 1, dp)
		if j > 0 and B[j - 1] == C[k - 1]:
			temp = temp or self.rec_sol(A, B, C, i, j - 1, k - 1, dp)
		dp[i][j][k] = temp
		return temp

	def dp_sol(self, A, B, C):
		len_A = len(A)
		len_B = len(B)
		dp = np.array([[0] * (len_B + 1)] * (len_A + 1))
		for i in range(len_A + 1):
			for j in range(len_B + 1):
				if i == 0 and j == 0:
					dp[0][0] = 1
				elif i == 0 and C[j - 1] == B[j - 1]:
					dp[i][j] = dp[i][j - 1]
				elif j == 0 and C[i - 1] == A[i - 1]:
					dp[i][j] = dp[i - 1][j]
				elif C[i + j - 1] == A[i - 1] and C[i + j - 1] == B[j - 1]:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
				elif C[i + j - 1] == A[i - 1]:
					dp[i][j] = dp[i - 1][j]
				elif C[i + j - 1] == B[j - 1]:
					dp[i][j] = dp[i][j - 1]
		return dp[len_A][len_B]

	def isInterleave(self, A, B, C):
		if len(A) + len(B) != len(C):
			return 0
		return self.dp_sol(A, B, C)


class Solution:

	def isInterleave(self, A, B, C):
		(X, Y, S) = (A, B, C)
		(M, N) = (len(X), len(Y))
		if M + N != len(S):
			return False
		T = [[False for x in range(N + 1)] for y in range(M + 1)]
		for i in range(0, M + 1):
			for j in range(0, N + 1):
				if i == 0 and j == 0:
					T[i][j] = True
				elif i and j and (X[i - 1] == S[i + j - 1]) and (Y[j - 1] == S[i + j - 1]):
					T[i][j] = T[i - 1][j] or T[i][j - 1]
				elif i and X[i - 1] == S[i + j - 1]:
					T[i][j] = T[i - 1][j]
				elif j and Y[j - 1] == S[i + j - 1]:
					T[i][j] = T[i][j - 1]
		return T[M][N]


class Solution:

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


class Solution:

	def isInterleave(self, A, B, C):
		a = len(A)
		b = len(B)
		stateMap = [[False for _ in range(a + 1)] for i in range(b + 1)]
		stateMap[0][0] = True
		for i in range(1, a + 1):
			stateMap[0][i] = C[i - 1] == A[i - 1]
		for i in range(1, b + 1):
			stateMap[i][0] = C[i - 1] == B[i - 1]
		for r in range(1, b + 1):
			for c in range(1, a + 1):
				stateMap[r][c] = stateMap[r][c - 1] and A[c - 1] == C[r + c - 1] or (stateMap[r - 1][c] and B[r - 1] == C[r + c - 1])
		return stateMap[b][a]


class Solution:

	def isInterleave(self, s1, s2, s3):
		memo = {}

		def dfs(i, j, k):
			if i == len(s2):
				return s1[j:] == s3[k:]
			if j == len(s1):
				return s2[i:] == s3[k:]
			ans = False
			if (i, j) in memo:
				return memo[i, j]
			else:
				ans = s2[i] == s3[k] and dfs(i + 1, j, k + 1) or (s1[j] == s3[k] and dfs(i, j + 1, k + 1))
				memo[i, j] = ans
			return memo[i, j]
		if len(s1) + len(s2) != len(s3):
			return False
		else:
			return dfs(0, 0, 0)


class Solution:

	def isInterleave(self, A, B, C):
		memo = {}
		return self.solve(A, B, C, len(A), len(B), len(C), memo)

	def solve(self, A, B, C, n, m, k, memo):
		if k == 0:
			return True
		key = str(n) + '-' + str(m) + '-' + str(k)
		if key in memo:
			return memo[key]
		atake = False
		btake = False
		if n > 0 and A[n - 1] == C[k - 1]:
			atake = self.solve(A, B, C, n - 1, m, k - 1, memo)
		if m > 0 and B[m - 1] == C[k - 1]:
			btake = self.solve(A, B, C, n, m - 1, k - 1, memo)
		if atake or btake:
			memo[key] = True
		else:
			memo[key] = False
		return memo[key]


class Solution:

	def solve(self, A, B, C, i, j, k, dp):
		if k == len(C):
			return True
		if dp[i][j] != -1:
			return dp[i][j]
		(ans1, ans2) = (0, 0)
		if i < len(A) and A[i] == C[k]:
			ans1 = self.solve(A, B, C, i + 1, j, k + 1, dp)
		if j < len(B) and B[j] == C[k]:
			ans2 = self.solve(A, B, C, i, j + 1, k + 1, dp)
		dp[i][j] = ans1 or ans2
		return dp[i][j]

	def isInterleave(self, A, B, C):
		if len(A) + len(B) != len(C):
			return False
		dp = [[-1 for i in range(len(B) + 1)] for j in range(len(A) + 1)]
		a = self.solve(A, B, C, 0, 0, 0, dp)
		return a


class Solution:

	def isInterleave(self, A, B, C):

		def inter(a, b, c, i, j, k, dp):
			if k == 0:
				return 1
			if dp[i][j] != -1:
				return dp[i][j]
			x = 0
			y = 0
			if i - 1 >= 0 and a[i - 1] == c[k - 1]:
				x = inter(a, b, c, i - 1, j, k - 1, dp)
			if j - 1 >= 0 and b[j - 1] == c[k - 1]:
				y = inter(a, b, c, i, j - 1, k - 1, dp)
			dp[i][j] = x or y
			return dp[i][j]
		dp = [[-1 for i in range(len(B) + 1)] for j in range(len(A) + 1)]
		return inter(A, B, C, len(A), len(B), len(C), dp)


class Solution:

	def get(self, i, j, k, a, b, n, m, c, dp):
		if i == n and j == m:
			return 1
		if dp[i][j] != -1:
			return dp[i][j]
		ans = 0
		if i == n:
			if b[j] == c[k]:
				ans = self.get(i, j + 1, k + 1, a, b, n, m, c, dp)
			else:
				ans = 0
		elif j == m:
			if a[i] == c[k]:
				ans = self.get(i + 1, j, k + 1, a, b, n, m, c, dp)
			else:
				ans = 0
		elif a[i] == c[k] and b[j] == c[k]:
			ans = self.get(i + 1, j, k + 1, a, b, n, m, c, dp) | self.get(i, j + 1, k + 1, a, b, n, m, c, dp)
		elif b[j] == c[k]:
			ans = ans | self.get(i, j + 1, k + 1, a, b, n, m, c, dp)
		elif a[i] == c[k]:
			ans = ans | self.get(i + 1, j, k + 1, a, b, n, m, c, dp)
		else:
			ans = 0
		dp[i][j] = ans
		return ans

	def isInterleave(self, a, b, c):
		dp = []
		n = len(a)
		m = len(b)
		if len(c) != len(a) + len(b):
			return False
		for i in range(0, n + 1):
			dp.append([-1 for j in range(0, m + 1)])
		val = self.get(0, 0, 0, a, b, n, m, c, dp)
		return val


class Solution:

	def isInterleave(self, a, b, c):
		if len(a) + len(b) != len(c):
			return False
		res = [True for i in range(len(b) + 1)]
		temp = [True for i in range(len(b) + 1)]
		for i in range(1, len(a) + 1):
			for j in range(1, len(b) + 1):
				res[j] = a[i - 1] == c[i + j - 1] and temp[j] or (b[j - 1] == c[i + j - 1] and res[j - 1])
			temp = res
			res = [True for i in range(len(b) + 1)]
		return temp[len(b)]


class Solution:

	def isInterleave(self, a, b, c):
		if len(a) + len(b) != len(c):
			return False
		dp = [[-1 for i in range(len(b) + 1)] for i in range(len(a) + 1)]
		for i in range(len(a)):
			dp[i][0] = True
		for i in range(len(b)):
			dp[0][i] = True
		for i in range(1, len(a) + 1):
			for j in range(1, len(b) + 1):
				dp[i][j] = a[i - 1] == c[i + j - 1] and dp[i - 1][j] or (b[j - 1] == c[i + j - 1] and dp[i][j - 1])
		return dp[len(a)][len(b)]


class Solution:

	def isInterleave1(self, A, B, C):
		global dp
		if len(C) == 0 and len(A) == 0 and (len(B) == 0):
			return 1
		if len(C) == 0 and (len(A) != 0 or len(B) != 0):
			return 0
		if dp.get((A, B, C)) != None:
			return dp[A, B, C]
		if len(A) > 0 and len(B) > 0 and (A[0] == C[0]) and (B[0] == C[0]):
			dp[A, B, C] = self.isInterleave1(A[1:], B, C[1:]) | self.isInterleave1(A, B[1:], C[1:])
			return dp[A, B, C]
		elif len(A) > 0 and A[0] == C[0]:
			dp[A, B, C] = self.isInterleave1(A[1:], B, C[1:])
			return dp[A, B, C]
		elif len(B) > 0 and B[0] == C[0]:
			dp[A, B, C] = self.isInterleave1(A, B[1:], C[1:])
			return dp[A, B, C]
		dp[A, B, C] = 0
		return dp[A, B, C]

	def isInterleave(self, A, B, C):
		global dp
		dp = {}
		return self.isInterleave1(A, B, C)


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def isInterleave(self, A, B, C):
		d = dict()

		def dfs(i, j):
			if i + j == len(C):
				return True
			if d.get((i, j)) != None:
				return d[i, j]
			if i == len(A):
				if B[j] != C[i + j]:
					return False
				d[i, j] = dfs(i, j + 1)
				return d[i, j]
			if j == len(B):
				if A[i] != C[i + j]:
					return False
				d[i, j] = dfs(i + 1, j)
				return d[i, j]
			if A[i] != C[i + j] and B[j] != C[i + j]:
				return False
			if A[i] == C[i + j] and B[j] == C[i + j]:
				d[i, j] = dfs(i + 1, j) or dfs(i, j + 1)
				return d[i, j]
			if A[i] == C[i + j]:
				d[i, j] = dfs(i + 1, j)
				return d[i, j]
			if B[j] == C[i + j]:
				d[i, j] = dfs(i, j + 1)
				return d[i, j]
		return dfs(0, 0)


class Solution:

	def isInterleave(self, s1, s2, s3):
		(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(1, m + 1):
			dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
		for j in range(1, n + 1):
			dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				choose_up = False
				choose_left = False
				if s1[i - 1] == s3[i + j - 1]:
					choose_up = dp[i - 1][j]
				if s2[j - 1] == s3[i + j - 1]:
					choose_left = dp[i][j - 1]
				dp[i][j] = choose_up or choose_left
		return dp[m][n]


class Solution:

	def isInterleave(self, a, b, c):
		n1 = len(a)
		n2 = len(b)
		n3 = len(c)
		if n1 + n2 != n3:
			return False
		dp = [[-1 for i in range(n2 + 1)] for j in range(n1 + 1)]

		def findsol(i, j, k, a, b, c, n1, n2, n3):
			if i + j == k and k == n3:
				return True
			if dp[i][j] != -1:
				return dp[i][j]
			ans = False
			if i < n1 and a[i] == c[k]:
				ans = ans or findsol(i + 1, j, k + 1, a, b, c, n1, n2, n3)
			if j < n2 and b[j] == c[k]:
				ans = ans or findsol(i, j + 1, k + 1, a, b, c, n1, n2, n3)
			dp[i][j] = ans
			return ans
		return findsol(0, 0, 0, a, b, c, n1, n2, n3)


def solver(a, b, c, ans, string, m, n, dct):
	if string != c[:len(string)]:
		return False
	if (m, n) in dct:
		return dct[m, n]
	if m == 0 and n == 0:
		if string == c:
			ans[0] = True
			return True
	(t1, t2) = (False, False)
	if m < 0:
		t1 = solver(a, b, c, ans, string + a[m], m + 1, n, dct)
		if t1:
			return t1
	if n < 0:
		t2 = solver(a, b, c, ans, string + b[n], m, n + 1, dct)
		if t2:
			return t2
	dct[m, n] = t1 or t2
	return t1 or t2

class Solution:

	def isInterleave(self, a, b, c):
		if len(a) + len(b) != len(c):
			return False
		if c[0] not in (a[0], b[0]) or c[-1] not in (a[-1], b[-1]):
			return False
		ans = [False]
		dct = dict()
		return solver(a, b, c, ans, '', -len(a), -len(b), dct)


from collections import defaultdict

class Solution:

	def isInterleave(self, A, B, C):
		lp = [[0 for i in range(len(B) + 1)] for j in range(len(A) + 1)]
		for i in range(len(A) + 1):
			for j in range(len(B) + 1):
				if i == 0 and j == 0:
					lp[i][j] = 1
				elif i == 0 and B[j - 1] == C[j - 1]:
					lp[i][j] = lp[i][j - 1]
				elif j == 0 and A[i - 1] == C[i - 1]:
					lp[i][j] = lp[i - 1][j]
				elif A[i - 1] == C[i + j - 1] and B[j - 1] != C[i + j - 1]:
					lp[i][j] = lp[i - 1][j]
				elif B[j - 1] == C[i + j - 1] and A[i - 1] != C[i + j - 1]:
					lp[i][j] = lp[i][j - 1]
				elif A[i - 1] == C[i + j - 1] and B[j - 1] == C[i + j - 1]:
					lp[i][j] = lp[i][j - 1] or lp[i - 1][j]
		return lp[len(A)][len(B)]


class Solution:

	def Interleaf(self, s1, s2, s3, i, j, dp):
		if i == -1 and j == -1:
			return True
		if i == -1:
			return s2[:j + 1] == s3[:j + 1]
		if j == -1:
			return s1[:i + 1] == s3[:i + 1]
		if dp[i][j] != -1:
			return dp[i][j]
		(ans, k) = (False, i + j + 1)
		if s3[k] != s1[i] and s3[k] != s2[j]:
			ans = False
		elif s3[k] == s1[i] and s3[k] == s2[j]:
			ans = self.Interleaf(s1, s2, s3, i - 1, j, dp) or self.Interleaf(s1, s2, s3, i, j - 1, dp)
		elif s3[k] == s1[i]:
			ans = self.Interleaf(s1, s2, s3, i - 1, j, dp)
		else:
			ans = self.Interleaf(s1, s2, s3, i, j - 1, dp)
		dp[i][j] = ans
		return ans

	def isInterleave(self, A, B, C):
		(s1, s2, s3) = (A, B, C)
		(i, j) = (len(s1), len(s2))
		dp = [[-1 for x in range(j)] for y in range(i)]
		if len(s3) != i + j:
			return False
		return self.Interleaf(s1, s2, s3, i - 1, j - 1, dp)


class Solution:

	def isInterleave(self, A, B, C):

		def manu(i, j, A, B, C):
			if i == len(A):
				return B[j:] == C[i + j:]
			if j == len(B):
				return A[i:] == C[i + j:]
			if dp[i][j] != -1:
				return dp[i][j]
			(x, y) = (0, 0)
			if A[i] == C[i + j]:
				x = manu(i + 1, j, A, B, C)
			if B[j] == C[i + j]:
				y = manu(i, j + 1, A, B, C)
			dp[i][j] = x or y
			return dp[i][j]
		dp = [[-1 for i in range(len(B))] for i in range(len(A))]
		return manu(0, 0, A, B, C)


class Solution:

	def isInterleave(self, A, B, C):
		n1 = len(A)
		n2 = len(B)
		n3 = len(C)
		if n3 != n1 + n2:
			return False
		dp = [[False for j in range(n2 + 1)] for i in range(n1 + 1)]
		for i in range(n1 + 1):
			for j in range(n2 + 1):
				if i == 0 and j == 0:
					dp[i][j] = True
				elif i == 0 and B[j - 1] == C[i + j - 1]:
					dp[i][j] = True
				elif j == 0 and C[i + j - 1] == A[i - 1]:
					dp[i][j] = True
				else:
					dp[i][j] = dp[i - 1][j] and C[i + j - 1] == A[i - 1] or (dp[i][j - 1] and C[i + j - 1] == B[j - 1])
		return dp[-1][-1]


class Solution:

	def isInterleave(self, a, b, c):
		(p, q, r) = (len(a), len(b), len(c))
		if p + q < r:
			return False
		cache = {}

		def dfs(x, y, z):
			if z >= r:
				return True
			if (x, y, z) in cache:
				return cache[x, y, z]
			if x < p and a[x] != c[z] and (y < q) and (b[y] != c[z]):
				cache[x, y, z] = False
				return False
			if x < p and a[x] == c[z]:
				if dfs(x + 1, y, z + 1):
					cache[x, y, z] = True
					return True
			if y < q and b[y] == c[z]:
				if dfs(x, y + 1, z + 1):
					cache[x, y, z] = True
					return True
			cache[x, y, z] = False
			return False
		return dfs(0, 0, 0)


class Solution:

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


class Solution:

	def isInterleave(self, A, B, C):
		if len(A) + len(B) != len(C):
			return 0
		dp = [[0] * (len(B) + 1) for i in range(len(A) + 1)]
		dp[0][0] = 1
		for i in range(1, len(A) + 1):
			dp[i][0] = 1 if A[:i] == C[:i] else 0
		for j in range(1, len(B) + 1):
			dp[0][j] = 1 if B[:j] == C[:j] else 0
		for i in range(1, len(A) + 1):
			for j in range(1, len(B) + 1):
				s = C[i + j - 1]
				if A[i - 1] == s:
					dp[i][j] = dp[i - 1][j]
				if B[j - 1] == s:
					dp[i][j] = dp[i][j] or dp[i][j - 1]
		return dp[len(A)][len(B)]


from itertools import product
from functools import lru_cache

class Solution:

	def isInterleave(self, A, B, C):
		(a, b, c) = (len(A), len(B), len(C))
		if a + b != c:
			return False

		@lru_cache(None)
		def dp(i, j):
			if i == a and j == b:
				return True
			return j <= b and dp(i, j + 1) and (B[j] == C[i + j]) or (i <= a and dp(i + 1, j) and (A[i] == C[i + j]))
		return dp(0, 0)


class Solution:

	def isInterleave(self, A, B, C):
		(a, b, c) = (len(A), len(B), len(C))
		if a + b != c:
			return False
		cache = {}

		def memo(i, j):
			if (i, j) in cache:
				return cache[i, j]
			if i == a and j == b:
				return True
			if i < a and memo(i + 1, j) and (A[i] == C[i + j]):
				return True
			if j < b and memo(i, j + 1) and (B[j] == C[i + j]):
				return True
			cache[i, j] = False
			return False
		return memo(0, 0)


class Solution:

	def isInterleave(self, A, B, C):
		d = {}

		def find(i, j, k):
			if i == 0:
				if B[:j] == C[:k]:
					return True
				return False
			if j == 0:
				if A[:i] == C[:k]:
					return True
				return False
			if k == 0:
				return False
			if (i, j, k) in d:
				return d[i, j, k]
			(a, b) = (False, False)
			if A[i - 1] == C[k - 1]:
				a = find(i - 1, j, k - 1)
			if B[j - 1] == C[k - 1]:
				b = find(i, j - 1, k - 1)
			d[i, j, k] = False
			if a or b:
				d[i, j, k] = True
			return d[i, j, k]
		return find(len(A), len(B), len(C))


class Solution:

	def isInterleave(self, A, B, C):
		hmap = {}
		if len(C) != len(A) + len(B):
			return False

		def interleaved(A, B, C, i, j, k):
			if i == len(A) and j == len(B) and (k == len(C)):
				return 1
			if (i, j, k) not in hmap:
				(a, b) = (0, 0)
				if i < len(A) and A[i] == C[k]:
					a = interleaved(A, B, C, i + 1, j, k + 1)
				if j < len(B) and B[j] == C[k]:
					b = interleaved(A, B, C, i, j + 1, k + 1)
				hmap[i, j, k] = a + b
			return hmap[i, j, k]
		ans = interleaved(A, B, C, 0, 0, 0)
		if ans:
			return True
		return False


class Solution:

	def isInterleave(self, A, B, C):
		x = len(A)
		y = len(B)
		z = len(C)
		dp = [[-1 for i in range(y + 1)] for i in range(x + 1)]

		def recursion(x, y, z, dp):
			if x == 0 and y == 0:
				return True
			if dp[x][y] != -1:
				return dp[x][y]
			First = False
			Second = False
			if x > 0 and z > 0 and (A[x - 1] == C[z - 1]):
				First = recursion(x - 1, y, z - 1, dp)
			if y > 0 and z > 0 and (B[y - 1] == C[z - 1]):
				Second = recursion(x, y - 1, z - 1, dp)
			dp[x][y] = First or Second
			return dp[x][y]
		return recursion(x, y, z, dp)


class Solution:

	def help(self, i, j, k, A, B, C, dp):
		if i == len(A) and j == len(B) and (k == len(C)):
			return 1
		if dp[i][j] != -1:
			return dp[i][j]
		ans1 = 0
		ans2 = 0
		if i < len(A) and A[i] == C[k]:
			ans1 = self.help(i + 1, j, k + 1, A, B, C, dp)
		if j < len(B) and B[j] == C[k]:
			ans2 = self.help(i, j + 1, k + 1, A, B, C, dp)
		dp[i][j] = ans1 + ans2
		return dp[i][j]

	def isInterleave(self, A, B, C):
		i = 0
		j = 0
		k = 0
		dp = [[-1 for i in range(len(B) + 1)] for j in range(len(A) + 1)]
		if len(A) + len(B) != len(C):
			return 0
		return self.help(i, j, k, A, B, C, dp)


class Solution:

	def __is_inter_leave_helper(self, i, j, k, a, b, c):
		if i == len(a) and j == len(b) and (k == len(c)):
			return True
		if i == len(a):
			if j == len(b):
				return False
			while k < len(c):
				if b[j] != c[k]:
					return False
				j += 1
				k += 1
			return True
		if j == len(b):
			if i == len(a):
				return False
			while k < len(c):
				if a[i] != c[k]:
					return False
				i += 1
				k += 1
			return True
		if self.dp[i][j] == None:
			self.dp[i][j] = False
			if a[i] == c[k]:
				if self.__is_inter_leave_helper(i + 1, j, k + 1, a, b, c):
					self.dp[i][j] = True
			if not self.dp[i][j] and b[j] == c[k]:
				if self.__is_inter_leave_helper(i, j + 1, k + 1, a, b, c):
					self.dp[i][j] = True
		return self.dp[i][j]

	def isInterleave(self, A, B, C):
		if len(C) != len(A) + len(B):
			return False
		self.dp = [[None for j in range(len(B))] for i in range(len(A))]
		return self.__is_inter_leave_helper(0, 0, 0, A, B, C)


class Solution:

	def isInterleave(self, A, B, C):
		return self.helper(A, B, C, {})

	def helper(self, str1, str2, combo, store):
		if not str1:
			return str2 == combo
		if not str2:
			return str1 == combo
		if (str1, str2) in store:
			return store[str1, str2]
		if str1[0] == combo[0] and self.helper(str1[1:], str2, combo[1:], store):
			store[str1, str2] = True
			return True
		if str2[0] == combo[0] and self.helper(str1, str2[1:], combo[1:], store):
			store[str1, str2] = True
			return True
		store[str1, str2] = False
		return False


class Solution:

	def isInterleave(self, A, B, C):
		if len(A) + len(B) != len(C):
			return False
		t = [[-1 for i in range(len(B) + 1)] for j in range(len(A) + 1)]

		def solve(i, j, k):
			if i == 0:
				return True
			if t[i][j] != -1:
				return t[i][j]
			if i > 0 and C[k - 1] == A[i - 1] and (j > 0) and (C[k - 1] == B[j - 1]):
				t[i][j] = solve(i - 1, j, k - 1) or solve(i, j - 1, k - 1)
				return t[i][j]
			if i > 0 and C[k - 1] == A[i - 1]:
				t[i][j] = solve(i - 1, j, k - 1)
				return t[i][j]
			if j > 0 and C[k - 1] == B[j - 1]:
				t[i][j] = solve(i, j - 1, k - 1)
				return t[i][j]
			t[i][j] = False
			return t[i][j]
		return solve(len(A), len(B), len(C))


class Solution:

	def isInterleave(self, A, B, C):
		a = len(A)
		b = len(B)
		if a + b != len(C):
			return 0
		table = [[-1 for i in range(a + 1)] for i in range(b + 1)]
		for i in range(b + 1):
			for j in range(a + 1):
				l = i + j - 1
				if i == 0 and j == 0:
					table[i][j] = 1
				elif i == 0 and C[l] == A[j - 1]:
					if table[0][j - 1]:
						table[i][j] = 1
					else:
						table[i][j] = 0
				elif j == 0 and C[l] == B[i - 1]:
					if table[i - 1][0]:
						table[i][j] = 1
					else:
						table[i][j] = 0
				else:
					if A[j - 1] == C[l] and table[i][j - 1]:
						z = 1
					else:
						z = 0
					if B[i - 1] == C[l] and table[i - 1][j]:
						x = 1
					else:
						x = 0
					table[i][j] = z or x
		return table[b][a]


class Solution:

	def isInterleave(self, A, B, C):
		X = len(A)
		Y = len(B)
		Z = len(C)
		dp = [[-1 for i in range(Y + 1)] for i in range(X + 1)]
		return self.recursion(A, B, C, X, Y, Z, dp)

	def recursion(self, A, B, C, X, Y, Z, dp):
		if X == 0 and Y == 0:
			return True
		if dp[X][Y] != -1:
			return dp[X][Y]
		First = False
		Second = False
		if X > 0 and Z > 0 and (A[X - 1] == C[Z - 1]):
			First = self.recursion(A, B, C, X - 1, Y, Z - 1, dp)
		if Y > 0 and Z > 0 and (B[Y - 1] == C[Z - 1]):
			Second = self.recursion(A, B, C, X, Y - 1, Z - 1, dp)
		dp[X][Y] = First or Second
		return dp[X][Y]


class Solution:

	def isInterleave(self, A, B, C):
		dp = []
		for _ in range(len(B) + 1):
			dp.append([-1] * (len(A) + 1))
		dp[0][0] = 0

		def add_index_to_right(row, col, index):
			new_row = row
			new_col = col + 1
			if col > len(A):
				return
			dp[new_row][new_col] = index

		def add_index_to_bottom(row, col, index):
			new_row = row + 1
			new_col = col
			if row > len(B):
				return
			dp[new_row][new_col] = index
		for row in range(0, len(B) + 1):
			for col in range(0, len(A) + 1):
				if dp[row][col] == -1:
					continue
				index_in_cell = dp[row][col]
				if col < len(A) and C[index_in_cell] == A[col]:
					add_index_to_right(row, col, index_in_cell + 1)
				if row < len(B) and C[index_in_cell] == B[row]:
					add_index_to_bottom(row, col, index_in_cell + 1)
		return 1 if dp[-1][-1] == len(C) else 0


import sys
sys.setrecursionlimit(1000000)
from collections import Counter

class Solution:

	def isInterleave(self, A, B, C):
		ab = A + B
		if not self.checkCount(ab, C):
			return False
		(self.a, self.b, self.c) = (A, B, C)
		self.aLength = len(A)
		self.bLength = len(B)
		self.cLength = len(C)
		(self.aPointer, self.bPointer, self.cPointer) = (0, 0, 0)
		return self.stormStrings(0, 0, 0)

	def checkCount(self, ab, C):
		abCount = Counter(ab)
		cCount = Counter(C)
		for char in abCount:
			if char not in cCount or cCount[char] != abCount[char]:
				return False
		return True

	def stormStrings(self, aP, bP, cP):
		while cP < self.cLength:
			if aP < self.aLength and self.a[aP] == self.c[cP]:
				if bP < self.bLength and self.b[bP] == self.c[cP]:
					bPath = self.stormStrings(aP, bP + 1, cP + 1)
					if bPath:
						return bPath
				aP += 1
				cP += 1
				continue
			elif bP < self.bLength and self.b[bP] == self.c[cP]:
				bP += 1
				cP += 1
				continue
			return False
		return True


class Solution:

	def isInterleave(self, A, B, C):
		n = len(A)
		m = len(B)
		p = len(C)
		if n + m != p:
			return False
		dp = [[-1] * (m + 1) for _ in range(n + 1)]

		def fun(i, j, idx, dp, n, m, p):
			if i == n and j == m and (idx == p):
				return True
			if dp[i][j] != -1:
				return dp[i][j]
			(p1, p2) = (False, False)
			if i < n and idx < p and (A[i] == C[idx]):
				p1 = fun(i + 1, j, idx + 1, dp, n, m, p)
			if j < m and idx < p and (B[j] == C[idx]):
				p2 = fun(i, j + 1, idx + 1, dp, n, m, p)
			dp[i][j] = p1 or p2
			return dp[i][j]
		return fun(0, 0, 0, dp, n, m, p)


class Solution:

	def recur(self, i, j, k, a, b, c):
		try:
			if i >= len(a) and j >= len(b) and (k >= len(c)):
				return True
			if k >= len(c) and (i < len(a) or j < len(b)):
				return False
			flag1 = i < len(a) and a[i] == c[k] and self.recur(i + 1, j, k + 1, a, b, c)
			flag2 = j < len(b) and b[j] == c[k] and self.recur(i, j + 1, k + 1, a, b, c)
			return flag1 or flag2
		except Exception as e:
			print('e', a, b, c, i, j, k)

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


class Solution:

	def solve(self, a, b, c, dp, n, m, i):
		if i == 0:
			return True
		if dp[n][m] != -1:
			return dp[n][m]
		x = y = False
		if n - 1 >= 0 and a[n - 1] == c[i - 1]:
			x = self.solve(a, b, c, dp, n - 1, m, i - 1)
		if m - 1 >= 0 and b[m - 1] == c[i - 1]:
			y = self.solve(a, b, c, dp, n, m - 1, i - 1)
		dp[n][m] = x or y
		return dp[n][m]

	def isInterleave(self, A, B, C):
		n = len(A)
		m = len(B)
		if n + m != len(C):
			return False
		dp = [[-1] * (m + 1) for _ in range(n + 1)]
		return self.solve(A, B, C, dp, n, m, len(C))


class Solution:

	def isInterleave(self, s1, s2, s3):

		def dfs(i1, i2):
			if i1 == len(s1) and i2 == len(s2):
				return True
			if (i1, i2) in mem:
				return mem[i1, i2]
			if i1 < len(s1) and s1[i1] == s3[i1 + i2]:
				if dfs(i1 + 1, i2):
					mem[i1, i2] = True
					return True
			if i2 < len(s2) and s2[i2] == s3[i1 + i2]:
				if dfs(i1, i2 + 1):
					mem[i1, i2] = True
					return True
			mem[i1, i2] = False
			return False
		if len(s1) + len(s2) != len(s3):
			return False
		mem = {}
		return dfs(0, 0)


class Solution:

	def isInterleave(self, A, B, C):

		def helper(one, two, three, i, j, cache):
			if cache[i][j] is not None:
				return cache[i][j]
			k = i + j
			if k == len(three):
				return True
			if i < len(one) and one[i] == three[k]:
				cache[i][j] = helper(one, two, three, i + 1, j, cache)
				if cache[i][j]:
					return True
			if j < len(two) and two[j] == three[k]:
				cache[i][j] = helper(one, two, three, i, j + 1, cache)
				return cache[i][j]
			return False
		if len(C) != len(A) + len(B):
			return False
		cache = [[None for i in range(len(B) + 1)] for j in range(len(A) + 1)]
		return helper(A, B, C, 0, 0, cache)


class Solution:

	def isInterleave(self, A, B, C):

		def dfs(i, j):
			if i == len(A):
				return B[j] == C[i + j]
			if j == len(B):
				return A[i] == C[i + j]
			if dp[i][j] != -1:
				return dp[i][j]
			ans = False
			ans = A[i] == C[i + j] and dfs(i + 1, j) or (B[j] == C[i + j] and dfs(i, j + 1))
			dp[i][j] = ans
			return dp[i][j]
		dp = [[-1 for i in range(len(B))] for j in range(len(A))]
		return dfs(0, 0)


class Solution:

	def isInterleave(self, a, b, c):
		dp = [[0 for i in range(len(b) + 1)] for j in range(len(a) + 1)]
		for i in range(len(a) + 1):
			for j in range(len(b) + 1):
				if i == 0 and j == 0:
					dp[i][j] = 1
				elif a[i - 1] == c[i + j - 1] and dp[i - 1][j] == 1:
					dp[i][j] = 1
				elif b[j - 1] == c[i + j - 1] and dp[i][j - 1] == 1:
					dp[i][j] = 1
		if dp[len(a)][len(b)] == 1:
			return 1
		else:
			return 0


class Solution:

	def isInterleave(self, a, b, c):
		i = j = k = 0
		n1 = len(a)
		n2 = len(b)
		n3 = len(c)
		dp = [[0 for _ in range(n2 + 1)] for _ in range(n1 + 1)]
		if n3 != n1 + n2:
			return 0
		for i in range(n1 + 1):
			for j in range(n2 + 1):
				if i == 0 and j == 0:
					dp[i][j] = True
				elif i == 0:
					if b[j - 1] == c[j - 1]:
						dp[i][j] = dp[i][j - 1]
				elif j == 0:
					if c[i - 1] == a[i - 1]:
						dp[i][j] = dp[i - 1][j]
				elif a[i - 1] == c[i + j - 1] and b[j - 1] != c[i + j - 1]:
					dp[i][j] = dp[i - 1][j]
				elif a[i - 1] != c[i + j - 1] and b[j - 1] == c[i + j - 1]:
					dp[i][j] = dp[i][j - 1]
				elif a[i - 1] == c[i + j - 1] and b[j - 1] == c[i + j - 1]:
					dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
		return dp[n1][n2]


class Solution:

	def isInterleave(self, A, B, C):
		memo = {}

		def is_inter_leave(x, y, z):
			if (x, y, z) not in memo:
				if z >= len(C):
					memo[x, y, z] = x == len(A) and y == len(B)
				else:
					result = False
					if x < len(A) and A[x] == C[z]:
						result = result or is_inter_leave(x + 1, y, z + 1)
					if y < len(B) and B[y] == C[z]:
						result = result or is_inter_leave(x, y + 1, z + 1)
					memo[x, y, z] = result
			return memo[x, y, z]
		if len(A) + len(B) != len(C):
			return False
		is_inter_leave(0, 0, 0)
		return memo[0, 0, 0]


class Solution:
	h = dict()

	def solve(self, A, B, C, l1, l2, l3):
		if l1 == 0:
			if B[:l2] == C[:l3]:
				return 1
			else:
				return 0
		elif l2 == 0:
			if A[:l1] == C[:l3]:
				return 1
			else:
				return 0
		elif (l1, l2, l3) in self.h:
			return self.h[l1, l2, l3]
		elif A[l1 - 1] == C[l3 - 1] and B[l2 - 1] != C[l3 - 1]:
			ans = self.solve(A, B, C, l1 - 1, l2, l3 - 1)
			self.h[l1, l2, l3] = ans
			return ans
		elif B[l2 - 1] == C[l3 - 1] and A[l1 - 1] != C[l3 - 1]:
			ans = self.solve(A, B, C, l1, l2 - 1, l3 - 1)
			self.h[l1, l2, l3] = ans
			return ans
		elif A[l1 - 1] == C[l3 - 1] and B[l2 - 1] == C[l3 - 1]:
			ans = self.solve(A, B, C, l1 - 1, l2, l3 - 1) or self.solve(A, B, C, l1, l2 - 1, l3 - 1)
			self.h[l1, l2, l3] = ans
			return ans
		else:
			self.h[l1, l2, l3] = 0
			return 0

	def isInterleave(self, A, B, C):
		if len(C) != len(A) + len(B):
			return 0
		else:
			ans = self.solve(A, B, C, len(A), len(B), len(C))
			self.h.clear()
			return ans


from functools import lru_cache

class Solution:

	def isInterleave(self, s1, s2, s3):
		dp = {}

		def dfs(i, j):
			if i == len(s1) and j == len(s2):
				return True
			if (i, j) in dp:
				return dp[i, j]
			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
			dp[i, j] = False
			return False
		return dfs(0, 0)


class Solution:

	def isInterleave(self, A, B, C):
		m = len(A)
		n = len(B)
		k = len(C)
		if m + n != k:
			return False
		if m == 0:
			return B == C
		if n == 0:
			return A == C
		dpTable = [[False] * (m + 1) for _ in range(n + 1)]
		dpTable[0][0] = True
		for col in range(1, len(dpTable[0])):
			dpTable[0][col] = dpTable[0][col - 1] and A[col - 1] == C[col - 1]
		for row in range(1, len(dpTable)):
			dpTable[row][0] = dpTable[row - 1][0] and (dpTable[row - 1][0] and B[row - 1] == C[row - 1])
		for row in range(1, len(dpTable)):
			for col in range(1, len(dpTable[0])):
				dpTable[row][col] = dpTable[row - 1][col] and B[row - 1] == C[row + col - 1] or (dpTable[row][col - 1] and A[col - 1] == C[row + col - 1])
		return dpTable[-1][-1]


class Solution:

	def isInterleave(self, A, B, C):

		def helper(A, B, C, k, i, j, memo):
			if (i, j, k) in memo:
				return memo[i, j, k]
			if i == len(B) and j == len(C) and (k == len(A)):
				return True
			if i < len(B) and A[k] == B[i]:
				if helper(A, B, C, k + 1, i + 1, j, memo):
					memo[i, j, k] = True
					return True
			if j < len(C) and A[k] == C[j]:
				if helper(A, B, C, k + 1, i, j + 1, memo):
					memo[i, j, k] = True
					return True
			memo[i, j, k] = False
			return False
		memo = {}
		return helper(C, A, B, 0, 0, 0, memo)


class Solution:

	def isInterleave(self, A, B, C):
		if len(A) + len(B) != len(C):
			return False
		has = {}

		def solve(i, j, r, a, b, c):
			if r >= len(c):
				if i >= len(a) and j >= len(b):
					return True
				return False
			key = str(i) + '*' + str(j) + '*' + str(r)
			if key in has:
				return has[key]
			res = False
			if i < len(a) and c[r] == a[i]:
				res = res or solve(i + 1, j, r + 1, a, b, c)
			if j < len(b) and c[r] == b[j]:
				res = res or solve(i, j + 1, r + 1, a, b, c)
			has[key] = res
			return res
		return solve(0, 0, 0, A, B, C)


class Solution:

	def isInterleave(self, A, B, C):
		if len(A) + len(B) != len(C):
			return False
		mapp = {}

		def util(i, j, k, mapp):
			if (i, j) in mapp:
				return mapp[i, j]
			if k == len(C):
				return True
			(a, b) = (False, False)
			if i < len(A) and A[i] == C[k]:
				a = util(i + 1, j, k + 1, mapp)
			if j < len(B) and B[j] == C[k]:
				b = util(i, j + 1, k + 1, mapp)
			mapp[i, j] = a or b
			return mapp[i, j]
		return util(0, 0, 0, mapp)


class Solution:

	def isInterleave(self, A, B, C):
		n = len(A)
		m = len(B)
		if n + m != len(C):
			return False
		dp = {}

		def rec(i, j):
			if i == n and j == m:
				return True
			if (i, j) in dp:
				return dp[i, j]
			if i < n and A[i] == C[i + j] and (rec(i + 1, j) == True):
				dp[i, j] = True
				return True
			if j < m and B[j] == C[i + j] and (rec(i, j + 1) == True):
				dp[i, j] = True
				return True
			dp[i, j] = False
			return False
		return rec(0, 0)


from functools import lru_cache

class Solution:

	def isInterleave(self, s1, s2, s3):

		@lru_cache(None)
		def dp(i, j, k):
			if i == len(s1) and j == len(s2) and (k == len(s3)):
				return True
			if k == len(s3):
				return False
			flag1 = False
			if i < len(s1) and s1[i] == s3[k]:
				flag1 = dp(i + 1, j, k + 1)
			flag2 = False
			if j < len(s2) and s2[j] == s3[k]:
				flag2 = dp(i, j + 1, k + 1)
			return flag1 or flag2
		return dp(0, 0, 0)