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 ifs2 is a scrambled string of s1.
Have you met this question in a real interview?
Yes
Example
Challenge
O(n3) time
LeetCode上的原题，请参见我之前的博客Scramble String。
解法一：
class Solution {
public:
/**
* @param s1 A string
* @param s2 Another string
* @return whether s2 is a scrambled string of s1
*/
bool isScramble(string& s1, string& s2) {
if (s1 == s2) return true;
if (s1.size() != s2.size()) return false;
string t1 = s1, t2 = s2;
sort(t1.begin(), t1.end());
sort(t2.begin(), t2.end());
if (t1 != t2) return false;
int n = s1.size();
for (int i = ; i < s1.size(); ++i) {
string a1 = s1.substr(, i), b1 = s1.substr(i), a2 = s2.substr(, i), b2 = s2.substr(i);
string a3 = s2.substr(n - i), b3 = s2.substr(, n - i);
if ((isScramble(a1, a2) && isScramble(b1, b2)) || (isScramble(a1, a3) && isScramble(b1, b3))) {
return true;
}
}
return false;
}
};
解法二：
class Solution {
public:
/**
* @param s1 A string
* @param s2 Another string
* @return whether s2 is a scrambled string of s1
*/
bool isScramble(string& s1, string& s2) {
if (s1 == s2) return true;
if (s1.size() != s2.size()) return false;
int n = s1.size();
vector<vector<vector<bool>>> dp(n, vector<vector<bool>>(n, vector<bool>(n + , false)));
for (int i = n - ; i >= ; --i) {
for (int j = n - ; j >= ; --j) {
for (int k = ; k <= n - max(i, j); ++k) {
if (s1.substr(i, k) == s2.substr(j, k)) {
dp[i][j][k] = true;
} else {
for (int t = ; t < k; ++t) {
if ((dp[i][j][t] && dp[i + t][j + t][k - t]) || (dp[i][j + k - t][t] && dp[i + t][j][k - t])) {
dp[i][j][k] = true;
break;
}
}
}
}
}
}
return dp[][][n];
}
};
解法三：
class Solution {
public:
/**
* @param s1 A string
* @param s2 Another string
* @return whether s2 is a scrambled string of s1
*/
bool isScramble(string& s1, string& s2) {
if (s1 == s2) return true;
if (s1.size() != s2.size()) return false;
int n = s1.size(), m[] = {};
for (int i = ; i < n; ++i) {
++m[s1[i] - 'a'];
--m[s2[i] - 'a'];
}
for (int i = ; i < ; ++i) {
if (m[i] != ) return false;
}
for (int i = ; i < n; ++i) {
string a1 = s1.substr(, i), b1 = s1.substr(i);
string a2 = s2.substr(, i), b2 = s2.substr(i), a3 = s2.substr(n - i), b3 = s2.substr(, n - i);
if ((isScramble(a1, a2) && isScramble(b1, b2)) || (isScramble(a1, a3) && isScramble(b1, b3))) {
return true;
}
}
return false;
}
};