# QUESTION

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”:

1 2 3 4 5 6 7 |
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”.

1 2 3 4 5 6 7 |
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”.

1 2 3 4 5 6 7 |
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.

This question is provided by Leetocode.

# Solution

The idea is dynamic program. Thank enieagle’s post.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
class Solution { public: int CHAR_SIZE = 26; bool isScramble(string s1, string s2) { return isScrambleHelper(s1, s2); } bool isScrambleHelper(string &s1, string &s2) { if (s1.size() != s2.size()) return false; if (s1 == s2) return true; int size = s1.size(); vector<int> bucket(CHAR_SIZE, 0); string s11, s12, s21, s22; // Check wheter they have the same chars for (int i = 0; i < s1.size(); ++i) { bucket[s1[i] - 'a'] += 1; bucket[s2[i] - 'a'] -= 1; } for (int i = 0; i < CHAR_SIZE; ++i) { if (bucket[i] != 0) return false; } // "dynamic programming" // Thank Jimmy and Qing for pointing out my lies. // I lied, this implementation is not a DP. // In the very beginning, I used a matrix to record previous // results. When going through sub-strings from short to long, // the calculation depends on previous results. While, to // satisfy leetcode, (it was not happy with the amount of space // I used and I didn't want to take time to optimize it), here // is the second implementation. It is not DP anymore. Leetcode // is happy with the trade between time and space I made. for (int i = 1; i < size; ++i) { s11 = s1.substr(0, i); s12 = s1.substr(i); s21 = s2.substr(0, i); s22 = s2.substr(i); if (isScrambleHelper(s11, s21) && isScrambleHelper(s12, s22)) return true; s21 = s2.substr(size - i); s22 = s2.substr(0, size - i); if (isScrambleHelper(s11, s21) && isScrambleHelper(s12, s22)) return true; } return false; } }; |

Hey, neat code. Thanks for sharing.

I have a question: What is the complexity of this solution?

Hey, I didn’t think about this question. Lets have a try.

Let donate T(n) to be the time complexity of a n-character string. I am talking about the worst case…:(

Then,

Obviously, T(1) = 1

T(n) = Sum(T(k) * T(n – k)), k belongs to [0, n)

It should be worse than Catalan number. Thus, it’s complexity is at lease exponential level. Sorry about this rough answer. 🙂

Thank your for this question. Keep in touch.

[…] 可以用bucket sort 来check，可以吧sot的nlgn降低为n。 […]

I’m sorry to point that out, but this is not DP at all. This is clearly recursion since you are calling isScrambleHelper() inside itself, and it can not process through until the recursion call returns. There is indeed a DP solution to this problem however yours isn’t. The recursion version could pass OJ though.

Uh… From my point, it is.

Look at line 36, 41. When we deal with a sub-string, we separate it into two parts, and BOTH of them are processed. That’s the current result is based on previous results. My understanding is, DP is a method to solve a complex problem by breaking them into simpler sub-problem, then combining the solutions of the sub-problems to reach an overall solution. Drawing the call tree of this recursion function will help you understand why it is a DP solution.

Thanks for your reading.

(There is something wrong with my inbox. Emails from my website is filtered as spam. I should approve your comment ASA you left it. Sorry about that)

Neat code, but I agree with Jimmy that I don’t think this is a DP solution either. You didn’t record the result of your sub problems.

Try to draw a matrix. Take segments of s1 as x-axis, and what of s2 as y-axis. What you get is, every time you calculate a cell, it will take results from 2 cells calculated earlier. It is not that explicit, actually

Oh, got what you are saying. The previous replay is what I thought at very beginning. I implemented that idea, while it was failed due to too much spaces used. (Ok, I admit I used char as boolean. it will be better if i “compressed” them) And, this is my second implementation. Leetcode looks satisfied with the trade between time and space. I am changing the comment. Thanks for your reply.

Time Limit Exceeded for “tqxpxeknttgwoppemjkivrulaflayn”, “afaylnlurvikjmeppowgttnkexpxqt”

Lol. I didn’t try it out for several months. When I get a chance(I am in the quench time 🙁 ), I will investigate it.