Given a strings1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation ofs1 = "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 stringss1ands2of the same length, determine ifs2is a scrambled string ofs1.
Have you met this question in a real interview?
Yes
Example
O(n3) time
line 23 ++k not ++i , i undefined variable name
dp
line 24 k starting from 2 not 1 , otherwise will lead to error
line 29, 30 cannot use ||= there is no such operator
better initilize 27
line 25 26 , i j range less than len - k , otherwise may lead to wrong result
line 16 using const to have array like 17
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\) {
// Write your code here
if \(s1.size\(\) != s2.size\(\)\) {
return false;
}
if \(s1.empty\(\)\) {
return true;
}
int len = s1.size\(\);
bool dp\[len + 1\]\[len\]\[len\];
for \(int i = 0; i < len; ++i\) {
for \(int j = 0; j < len; ++j\) {
dp\[1\]\[i\]\[j\] = s1\[i\] == s2\[j\];
}
}
for \(int k = 2; k <= len; ++k\) {
for \(int i = 0; i <= len - k; ++i\) {
for \(int j = 0; j <= len - k; ++j\) {
dp\[k\]\[i\]\[j\] = false;
for \(int m = 1; m < k; ++m\) {
dp\[k\]\[i\]\[j\] = dp\[k\]\[i\]\[j\] \|\| \(dp\[m\]\[i\]\[j\] && dp\[k-m\]\[i+m\]\[j+m\]\);
dp\[k\]\[i\]\[j\] = dp\[k\]\[i\]\[j\] \|\| \(dp\[m\]\[i\]\[j+k-m\] && dp\[k-m\]\[i+m\]\[j\]\);
}
}
}
}
return dp\[len\]\[0\]\[0\];
}
};