why "abcd" "bdac" are not Scramble String?


  • 0
    Y

    I think I don't understand this quite well.
    Originally, I thought just count the char of both string, and if the count number are the same for all the characters then it should be a scramble string pair.
    Could someone explain a little bit about why this thought doesn't work?


  • 1
    S

    Firstly, you would need to understand how to split the string like "abdc".
    abcd
    /
    ab cd
    / \ /
    a b c d
    So no matter how to rotate (ab, cd, or abcd), the answer we could get are:
    abcd, bacd, abdc, badc, cdab, dcab, dcba, cdba

    There is no way, bd is together by rotating.


  • 1
    R

    In the question, binary tree is built "by partitioning it to two non-empty substrings recursively"
    you might also be able to get the following binary trees:
    abcd
    / \
    a bcd
    / \
    ...

    OR

     abcd
     / \
    

    abc d
    / \
    ...

    So there will be more combinations than you listed.
    But I guess you are right on conclusion, bdac is still not a possible output of tree leaf swap.


Log in to reply
 

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