# 87. Scramble String
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
Example 1:
Input: s1 = "great", s2 = "rgeat"
Output: true
Example 2:
Input: s1 = "abcde", s2 = "caebd"
Output: false
# Solution
Approach 1: memoized recursion (with early stopping).
Approach 2: 3D DP.
# Code (Python)
Approach 1:
def isScramble(self, s1: str, s2: str) -> bool:
# memoized recursion with early stopping
return self._is_scramble(s1, s2, {})
def _is_scramble(self, s1, s2, memo):
if s1 > s2: # enforce an ordering of the key
s1, s2 = s2, s1
if (s1, s2) in memo:
return memo[(s1, s2)]
if s1 == s2:
memo[(s1, s2)] = True
return True
# early stopping
if sorted(s1) != sorted(s2):
memo[(s1, s2)] = False
return False
for i in range(1, len(s1)):
if self._is_scramble(s1[:i], s2[:i], memo) and self._is_scramble(s1[i:], s2[i:], memo):
memo[(s1, s2)] = True
return True
if self._is_scramble(s1[:i], s2[-i:], memo) and self._is_scramble(s1[i:], s2[:-i], memo):
memo[(s1, s2)] = True
return True
memo[(s1, s2)] = False
return False
Approach 2:
def isScramble(self, s1: str, s2: str) -> bool:
# DP -- scramble[i][j][k]: s1[i:i+k] and s2[j:j+k] is scramble (substring of length k, starting at position i and j for s1 and s2)
# scramble[i][j][k] = (scramble[i][j][l] and scramble[i+l][j+l][k-l]) or (scramble[i][j+k-l][l] and scramble[i+l][j][k-l])
scramble = [[[False] * (len(s1) + 1) for _ in range(len(s1))] for _ in range(len(s1))]
for k in range(1, len(s1) + 1):
for i in range(len(s1) - k + 1):
for j in range(len(s1) - k + 1):
if k == 1:
scramble[i][j][k] = s1[i] == s2[j]
else:
is_scramble = False
for l in range(1, k):
if (scramble[i][j][l] and scramble[i+l][j+l][k-l]) or (scramble[i][j+k-l][l] and scramble[i+l][j][k-l]):
is_scramble = True
break
scramble[i][j][k] = is_scramble
return scramble[0][0][len(s1)]
# Code (C++)
Approach 1:
// stack-overflow
class Solution {
private:
unordered_map<string,bool> umap;
public:
bool isScramble(string s1, string s2) {
int n = s1.size();
if (n != s2.size())
return false;
if (n == 1)
return s1 == s2;
if (s1 == s2)
return true;
if (s1 > s2) // enforce an ordering of the key
{
std::swap(s1, s2);
}
string key = s1 + "," + s2;
if (umap.find(key) != umap.end())
return umap[key];
// early stopping
string tmp1 = s1;
string tmp2 = s2;
std::sort(tmp1.begin(), tmp1.end());
std::sort(tmp2.begin(), tmp2.end());
if (tmp1 != tmp2)
{
umap[key] = false;
return false;
}
for (int len = 1; len <= n; ++len)
{
if (isScramble(s1.substr(0, len), s2.substr(0, len)) &&
isScramble(s1.substr(len, n-len), s2.substr(len, n-len))
||
isScramble(s1.substr(0, len), s2.substr(n-len, len)) &&
isScramble(s1.substr(len, n-len), s2.substr(0, n-len)))
{
umap[key] = true;
return true;
}
}
umap[key] = false;
return false;
}
};
Approach 2:
class Solution {
public:
bool isScramble(string s1, string s2) {
int n = s1.size();
if (n != s2.size())
return false;
int match[n+1][n][n];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
match[1][i][j] = (s1[i] == s2[j]);
}
}
for (int len = 2; len <= n; ++len)
{
for (int i = 0; i+len <= n; ++i)
{
for (int j = 0; j+len <= n; ++j)
{
for (int k = 1; k < len; ++k)
{
match[len][i][j] =
(match[k][i][j] && match[len-k][i+k][j+k]) ||
(match[k][i][j+len-k] && match[len-k][i+k][j]);
if (match[len][i][j])
break;
}
}
}
}
return match[n][0][0];
}
};