Given two strings S1 and S2 of equal length, the task is to determine if S2 is a scrambled form of S1.
Scrambled string: Given string str, we can represent it as a binary tree by partitioning it into two non-empty substrings recursively.
Below is one possible representation of str = coder:
 
To scramble the string, we may choose any non-leaf node and swap its two children. 
Suppose, we choose the node co and swap its two children, it produces a scrambled string ocder.
Similarly, if we continue to swap the children of nodes der and er, it produces a scrambled string ocred.
Note: Scrambled string is not the same as an Anagram.
Print "Yes" if S2 is a scrambled form of S1 otherwise print "No".
Example 1:
Input: S1="coder", S2="ocder"
Output: Yes
Explanation: ocder is a scrambled 
form of coder.
    ocder
   /    \
  oc    der
 / \    
o   c  
As "ocder" can represent it 
as a binary tree by partitioning 
it into two non-empty substrings.
We just have to swap 'o' and 'c' 
to get "coder".
Example 2:
Input: S1="abcde", S2="caebd" 
Output: No
Explanation: caebd is not a 
scrambled form of abcde.
Your Task:
You don't need to read input or print anything. You only need to complete the function isScramble() which takes two strings S1 and S2 as input and returns a boolean value.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N^{2})
Constrains: 
S1.length = S2.length
S1.length<=31
S1 and S2 consist of lower-case English letters.

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: String algorithms

Complete search

Tree algorithms

Divide and conquer

Data structures

Starter code: #User function Template for python3



class Solution:

    def isScramble(self,S1: str, S2: str):

        ##code here



Solutions:
from collections import Counter
from functools import lru_cache

class Solution:

	@lru_cache(None)
	def isScramble(self, s1: str, s2: str):
		if Counter(s1) != Counter(s2):
			return False
		if len(s1) == 1:
			return True
		for i in range(1, len(s1)):
			if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]) or (self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i])):
				return True
		return False


from functools import lru_cache

class Solution:

	def isScramble(self, S1: str, S2: str) -> bool:

		@lru_cache(maxsize=None)
		def isScrambled(S1: str, S2: str) -> bool:
			if S1 == S2:
				return True
			s = ''.join(sorted(S1))
			t = ''.join(sorted(S2))
			if s != t:
				return False
			length = len(S1)
			for i in range(1, length):
				if isScrambled(S1[:i], S2[:i]) and isScrambled(S1[i:], S2[i:]):
					return True
				if isScrambled(S1[:i], S2[length - i:]) and isScrambled(S1[i:], S2[:length - i]):
					return True
			return False
		return isScrambled(S1, S2)


from functools import lru_cache

class Solution:

	@lru_cache(None)
	def isScramble(self, S1: str, S2: str):
		if S1 == S2:
			return True
		for i in range(1, len(S1)):
			if self.isScramble(S1[:i], S2[:i]) and self.isScramble(S1[i:], S2[i:]):
				return True
			if self.isScramble(S1[:i], S2[-i:]) and self.isScramble(S1[i:], S2[:len(S2) - i]):
				return True
		return False


class Solution:

	def isScramble(self, S1: str, S2: str):
		mp = {}

		def solve(a, b):
			if a == b:
				return True
			if len(a) <= 1:
				return False
			key = a + ' ' + b
			if mp.get(key) != None:
				return mp[key]
			n = len(a)
			flag = False
			for k in range(1, n):
				cond1 = solve(a[0:k], b[n - k:]) and solve(a[k:], b[0:n - k])
				cond2 = solve(a[0:k], b[0:k]) and solve(a[k:], b[k:])
				if cond1 or cond2:
					flag = True
					break
			mp[key] = flag
			return flag
		return solve(S1, S2)


class Solution:

	def isScramble(self, S1: str, S2: str):
		d = {}

		def solve(s1, s2):
			if s1 == s2:
				d[s1 + '#' + s2] = True
				return True
			if len(s1) == 1:
				d[s1 + '#' + s2] = False
				return False
			if s1 + '#' + s2 in d:
				return d[s1 + '#' + s2]
			for i in range(1, len(s1)):
				if solve(s1[:i], s2[:i]) and solve(s1[i:], s2[i:]) or (solve(s1[:i], s2[-i:]) and solve(s1[i:], s2[:-i])):
					d[s1 + '#' + s2] = True
					return True
			d[s1 + '#' + s2] = False
			return False
		if len(S1) != len(S2):
			return False
		return solve(S1, S2)


import collections

class Solution:

	def isScramble(self, a: str, b: str):
		mp = {}

		def solve(a, b):
			key = a + '_' + b
			if len(a) < 1:
				mp[key] = False
				return False
			if a == b:
				mp[key] = True
				return True
			if key in mp:
				return mp[key]
			for i in range(1, len(a)):
				if solve(a[:i], b[:i]) and solve(a[i:], b[i:]) or (solve(a[:i], b[-i:]) and solve(a[i:], b[:-i])):
					mp[key] = True
					return True
			mp[key] = False
			return False
		if len(a) != len(b):
			return False
		return solve(a, b)


class Solution:

	def isScramble(self, S1: str, S2: str, d={}):
		s1 = S1
		s2 = S2
		n1 = len(s1)
		n2 = len(s2)
		if n1 != n2:
			return False
		if n1 == 0:
			return True
		if s1 == s2:
			return True
		if n1 <= 1:
			return False
		key = s1 + s2
		if key in d:
			return d[key]
		flag = False
		for i in range(1, n1):
			C1 = self.isScramble(s1[:i], s2[n1 - i:], d) and self.isScramble(s1[i:], s2[:n1 - i], d)
			C2 = self.isScramble(s1[:i], s2[:i], d) and self.isScramble(s1[i:], s2[i:], d)
			if C1 or C2:
				flag = True
				break
		d[key] = flag
		return flag


class Solution:

	def __init__(self):
		self.hmap = {}

	def isScramble(self, S1: str, S2: str):
		return self.helper(S1, S2)

	def helper(self, s, t):
		if (s, t) in self.hmap:
			return self.hmap[s, t]
		n = len(s)
		if s == t:
			self.hmap[s, t] = True
			return True
		cnt = [0] * 26
		for i in range(0, n):
			cnt[ord(s[i]) - ord('a')] += 1
			cnt[ord(t[i]) - ord('a')] -= 1
		for i in range(0, 26):
			if cnt[i] != 0:
				self.hmap[s, t] = False
				return False
		for x in range(1, n):
			if self.helper(s[0:x], t[0:x]) and self.helper(s[x:], t[x:]):
				self.hmap[s, t] = True
				return True
			if self.helper(s[0:x], t[n - x:]) and self.helper(s[x:], t[:n - x]):
				self.hmap[s, t] = True
				return True
		self.hmap[s, t] = False
		return False


dic = {}

class Solution:

	def isScramble(self, S1: str, S2: str):
		if len(S1) == 0:
			return True
		if S1 == S2:
			return True
		if S1 + ' ' + S2 in dic:
			return dic[S1 + ' ' + S2]
		flag = False
		for i in range(1, len(S1)):
			if self.isScramble(S1[:i], S2[:i]) and self.isScramble(S1[i:], S2[i:]):
				flag = True
				break
			if self.isScramble(S1[:i], S2[-i:]) and self.isScramble(S1[i:], S2[:-i]):
				flag = True
				break
		dic[S1 + ' ' + S2] = flag
		return flag


import sys
sys.setrecursionlimit(100000)

class Solution:

	def __init__(self):
		self.dp = dict()

	def isScramble(self, S1: str, S2: str):
		if len(S1) != len(S2):
			return False
		if S1 == S2:
			return True
		if S1 + S2 in self.dp:
			return self.dp[S1 + S2]
		count_string = len(S1)
		for i in range(1, count_string):
			if self.isScramble(S1[0:i], S2[0:i]) and self.isScramble(S1[i:], S2[i:]):
				self.dp[S1 + S2] = True
				return self.dp[S1 + S2]
			if self.isScramble(S1[0:i], S2[-i:]) and self.isScramble(S1[i:], S2[0:count_string - i]):
				self.dp[S1 + S2] = True
				return self.dp[S1 + S2]
		self.dp[S1 + S2] = False
		return self.dp[S1 + S2]


class Solution:

	def __init__(self):
		self.mp = {}

	def isScramble(self, s1: str, s2: str):
		if s1 == s2:
			return True
		if len(s1) != len(s2):
			return False
		if s1 + ' ' + s2 in self.mp:
			return self.mp[s1 + ' ' + s2]
		n = len(s1)
		for i in range(1, n):
			if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):
				self.mp[s1 + ' ' + s2] = True
				return True
			elif self.isScramble(s1[:i], s2[n - i:]) and self.isScramble(s1[i:], s2[:n - i]):
				self.mp[s1 + ' ' + s2] = True
				return True
		self.mp[s1 + ' ' + s2] = False
		return False


class Solution:

	def isScramble(self, S1: str, S2: str):

		def helper(s1, s2, memo):
			if (s1, s2) in memo:
				return memo[s1, s2]
			if sorted(s1) != sorted(s2):
				memo[s1, s2] = False
				return False
			if s1 == s2:
				memo[s1, s2] = True
				return True
			for i in range(1, len(s1)):
				if helper(s1[:i], s2[:i], memo) and helper(s1[i:], s2[i:], memo) or (helper(s1[:i], s2[-i:], memo) and helper(s1[i:], s2[:-i], memo)):
					memo[s1, s2] = True
					return True
			memo[s1, s2] = False
			return False
		return helper(S1, S2, {})


class Solution:

	def isScramble(self, s1: str, s2: str):
		if len(s1) != len(s2):
			return False
		if s1 == s2:
			return True
		dp = {}

		def solve(s1, s2):
			n = len(s1)
			if s1 == s2:
				return True
			if s1 + '' + s2 in dp:
				return dp[s1 + '' + s2]
			dp[s1 + '' + s2] = False
			for i in range(1, n):
				solve1 = solve(s1[:i], s2[:i]) and solve(s1[i:], s2[i:])
				solve2 = solve(s1[:i], s2[n - i:]) and solve(s1[i:], s2[:n - i])
				if solve1 or solve2:
					dp[s1 + '' + s2] = True
			return dp[s1 + '' + s2]
		return solve(s1, s2)


class Solution:

	def isScramble(self, S1, S2):
		self.leftRight = [0, len(S1) - 1]
		self.string1 = S1
		self.string2 = S2
		self.tuples = [(0, len(S1) - 1)]
		self.failedCases = []
		for i in range(2):
			Return = self.switch(self.leftRight[i], i)
			if Return:
				return True
		return False

	def switch(self, idx, drtn=0):
		(mainTuple, mainIdx) = self.findTup(idx)
		locations = self.getLocations(idx, mainTuple)
		string2 = self.string2
		if locations:
			if drtn == 0:
				self.leftRight[0] += 1
			else:
				self.leftRight[1] -= 1
			if self.leftRight[0] == self.leftRight[1]:
				return True
			for index in locations:
				changed = 0
				if index > mainTuple[0]:
					changed += 1
					if drtn:
						self.tuples.append((mainTuple[0], index - 1))
					else:
						self.tuples.append((mainTuple[0] + 1, index))
				if index < mainTuple[1]:
					changed += 1
					if drtn:
						self.tuples.append((index, mainTuple[1] - 1))
					else:
						self.tuples.append((index + 1, mainTuple[1]))
				if not drtn:
					self.string2 = string2[:idx] + string2[index] + string2[idx:index] + string2[index + 1:]
				else:
					self.string2 = string2[:index] + string2[index + 1:idx + 1] + string2[index] + string2[idx + 1:]
				if self.string2 not in self.failedCases:
					for i in range(2):
						Result = self.switch(self.leftRight[i], i)
						if Result:
							return True
				for j in range(changed):
					self.tuples.pop()
			if drtn == 0:
				self.leftRight[0] -= 1
			else:
				self.leftRight[1] += 1
		else:
			self.failedCases.append(self.string2)
		self.string2 = string2
		self.tuples.insert(mainIdx, mainTuple)
		return False

	def findTup(self, idx):
		for i in range(len(self.tuples)):
			tup = self.tuples[i]
			if idx >= tup[0] and idx <= tup[1]:
				self.tuples.pop(i)
				return (tup, i)

	def getLocations(self, idx, tup):
		locations = []
		for i in range(tup[0], tup[1] + 1):
			if self.string1[idx] == self.string2[i]:
				locations.append(i)
		return locations


class Solution:

	def isScramble(self, S1: str, S2: str):
		(s1, s2) = (S1, S2)
		if len(s1) != len(s2) or sorted(s1) != sorted(s2):
			return False
		if s1 == s2:
			return True
		n = len(s1)
		dp = [[[-1] * n for _ in range(n)] for _ in range(n + 1)]
		for i in range(n):
			for j in range(n):
				dp[1][i][j] = s1[i] == s2[j]
		for k in range(2, n + 1):
			for i in range(n - k + 1):
				for j in range(n - k + 1):
					dp[k][i][j] = False
					for p in range(1, k):
						if dp[p][i][j] and dp[k - p][i + p][j + p] or (dp[p][i][j + k - p] and dp[k - p][i + p][j]):
							dp[k][i][j] = True
							break
		return dp[n][0][0]


class Solution:

	def isScramble(self, S1: str, S2: str):
		if len(S1) != len(S2):
			return False
		self.mappa = dict()
		self.s1 = S1
		self.s2 = S2
		self.n = len(S1)
		return self.func(0, 0, self.n)

	def func(self, ind1, ind2, size):
		fetch = self.mappa.get((ind1, ind2, size))
		if fetch is not None:
			return fetch
		else:
			ans = False
			if size == 1:
				ans = self.s1[ind1] == self.s2[ind2]
			for i in range(1, size):
				ans |= self.func(ind1, ind2, i) and self.func(ind1 + i, ind2 + i, size - i)
				ans |= self.func(ind1, ind2 + size - i, i) and self.func(ind1 + i, ind2, size - i)
			self.mappa[ind1, ind2, size] = ans
			return ans


class Solution:

	def isScramble(self, S1: str, S2: str):
		dic = dict()

		def sol(S1, S2, i, j, n, m):
			if j - i != m - n:
				return 0
			if j - i == 1 and S1[i] == S2[n]:
				return 1
			s = S1[i:j] + '_' + S2[n:m]
			if s in dic:
				return dic[s]
			for k in range(1, j - i):
				if sol(S1, S2, i, i + k, n, n + k) and sol(S1, S2, i + k, j, n + k, m) or (sol(S1, S2, i, i + k, m - k, m) and sol(S1, S2, i + k, j, n, m - k)):
					dic[s] = 1
					return dic[s]
			dic[s] = 0
			return dic[s]
		return sol(S1, S2, 0, len(S1), 0, len(S2))


class Solution:

	def __init__(self):
		self.scrambles = {}

	def isScramble(self, s1: str, s2: str) -> bool:
		if (s1, s2) in self.scrambles:
			return self.scrambles[s1, s2]
		if s1 == s2:
			self.scrambles[s1, s2] = True
			return True
		ls = len(s1)
		if ls == 1 or sorted(s1) != sorted(s2):
			self.scrambles[s1, s2] = False
			return False
		for i in range(1, ls):
			(s1_left, s1_right) = (s1[:i], s1[i:])
			(s2_left, s2_right) = (s2[:i], s2[i:])
			match1 = self.isScramble(s1_left, s2_left) and self.isScramble(s1_right, s2_right)
			(s2_left2, s2_right2) = (s2[:ls - i], s2[ls - i:])
			match2 = self.isScramble(s1_left, s2_right2) and self.isScramble(s1_right, s2_left2)
			if match1 or match2:
				self.scrambles[s1, s2] = True
				return True
		self.scrambles[s1, s2] = False


from collections import Counter
from functools import lru_cache

class Solution:

	@lru_cache(None)
	def isScramble(self, s1: str, s2: str):
		if Counter(s1) != Counter(s2):
			return False
		if len(s1) == 1:
			return True
		for i in range(1, len(s1)):
			if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]) or (self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i])):
				return True
		return False
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		(S1, S2) = input().split()
		if Solution().isScramble(S1, S2):
			print('Yes')
		else:
			print('No')


class Solution:

	def __init__(self):
		self.map = {}

	def isScramble(self, s1, s2):
		if (s1, s2) in self.map:
			return self.map[s1, s2]
		if len(s1) != len(s2):
			self.map[s1, s2] = False
			return False
		if s1 == s2:
			self.map[s1, s2] = True
			return True
		if sorted(s1) != sorted(s2):
			self.map[s1, s2] = False
			return False
		for i in range(1, len(s1)):
			if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):
				return True
			if self.isScramble(s1[:i], s2[len(s2) - i:]) and self.isScramble(s1[i:], s2[:len(s2) - i]):
				return True
		self.map[s1, s2] = False
		return False


class Solution:

	def isScramble(self, S1: str, S2: str):
		if S1 == '' or S2 == '':
			return True
		elif S1 == S2 or S1 == S2[::-1]:
			return True
		i = 1
		while i < len(S1):
			if self.match(S1[:i], S2[-i:]) and self.match(S1[i:], S2[:-i]):
				if S1[i:] + S1[:i] == S2:
					return True
				elif self.isScramble(S1[:i], S2[-i:]) and self.isScramble(S1[i:], S2[:-i]):
					return True
				return False
			elif self.match(S1[:i], S2[:i]) and self.match(S1[i:], S2[i:]):
				if self.isScramble(S1[:i], S2[:i]) and self.isScramble(S1[i:], S2[i:]):
					return True
				else:
					return False
			i += 1

	def match(self, s1, s2):
		s1 = list(s1)
		s2 = list(s2)
		s1.sort()
		s2.sort()
		if s1 != s2:
			return False
		return True


class Solution:

	def isScramble(self, s1: str, s2: str):
		hsh = {}
		return self.check(s1, s2, hsh)

	def check(self, s1, s2, hsh):
		n = len(s1)
		if s1 == s2:
			hsh[s1 + s1] = True
			return True
		if s1 + s2 in hsh:
			return hsh[s1 + s2]
		for i in range(1, n):
			a = s1[:i]
			b = s2[:i]
			c = s1[i:]
			d = s2[i:]
			if self.check(a, b, hsh) and self.check(c, d, hsh):
				hsh[s1 + s2] = True
				return True
			e = s1[:i]
			f = s2[n - i:]
			g = s1[i:]
			h = s2[0:n - i]
			if self.check(e, f, hsh) and self.check(g, h, hsh):
				hsh[s1 + s2] = True
				return True
		hsh[s1 + s2] = False
		return False