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 stringss1
ands2
of the same length, determine ifs2
is 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\];
}
};