Can you partition a string at ANY index at ANY time in producing a scramble?


  • 31
    D

    The example shows the case where left child ALWAYS has equal or one-less characters than right child. But since "abb" is a scramble of "bab", as suggested by a test case, strings are not always partitioned in the way as the example implies.

    However, if the answer is Yes, I think scrambles just become permutations. Isn't it?

    So I am so confused what is expected...

    Thanks!


  • 16
    G

    For instance, ABCDE. There exists no scramble like CAEBD under the given operations.


  • 0

    Hi, I'm also confused. I just wonder if scramble has transitivity.
    Since ABCDE => BACDE => BCADE => CABDE => CAEBD.
    By the way, it says we can do the swap any times.


  • 9
    J

    This is very important to understand the difference to come up with a solution for this problem.
    you can not generate all the permutations of s1 with only branch and swap of the branches.

    Permutation is like a grammar which is able to generate all the combinations while the branch and swap is like a push-down automata. The set of output strings will not be equal.


  • 1
    W

    you can not swap 'C' and 'A'


  • 0
    E

    swap AB with C => CABDE, swap BD with E=>CAEBD


  • 9
    E

    It will be much clear if the problem could describe how we can partition a String with an odd length.
    Inferring from the example, I arrived at the wrong under assumption that length of the left child can not be greater than that of its sibling, right child.


  • 1
    Z

    when you swap AB with C then you can't swap BD with E . you can draw a tree on the paper ..


  • 1

    Wow, two amazing names: grammar and push-down automata.


  • 1
    M

    The question's description is really confusing and insufficient. Someone please improve it.


  • 2
    L

    The key point is that you can build the BST only once.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.