Problem
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
/**
* @param {string} s1
* @param {string} s2
* @return {boolean}
*/
var isScramble = function(s1, s2) {
return helper({}, s1, s2);
};
var helper = function (dp, s1, s2) {
var map = {};
if (dp[s1 + s2] !== undefined) return dp[s1 + s2];
if (s1 === s2) return true;
for (var j = 0; j < s1.length; j++) {
if (map[s1[j]] === undefined) map[s1[j]] = 0;
if (map[s2[j]] === undefined) map[s2[j]] = 0;
map[s1[j]]++;
map[s2[j]]--;
}
for (var key in map) {
if (map[key] !== 0) {
dp[s1 + s2] = false;
return false;
}
}
for (var i = 1; i < s1.length; i++) {
if ((helper(dp, s1.substr(0, i), s2.substr(0, i))
&& helper(dp, s1.substr(i), s2.substr(i))) ||
(helper(dp, s1.substr(0, i), s2.substr(s2.length - i))
&& helper(dp, s1.substr(i), s2.substr(0, s2.length - i)))) {
dp[s1 + s2] = true;
return true;
}
}
dp[s1 + s2] = false;
return false;
};
Explain:
nope.
Complexity:
- Time complexity : O(n^4).
- Space complexity : O(n^4).