求问scramble string和anagram的区别

最近刷leetcode的时候碰到了scramble string的问题，很自然地联想到了anagram，因为想搞懂这两者的区别是什么。研究了leetcode题目的描述和discussion并且google了并没有得到很好的答案，问题主要集中在两个方面：1. recursively分substring的时候左右尺寸最多只能相差1么   比如：abcde -->a/bcde..... 然后在递归是可以的么
2.第二点是swap的时候，选一个，非叶节点swap，之后如果children还是非叶节点 还要继续recursively swap么  比如： abc                                                  bca                                  cba
                                                                                                                                                                        /  \                                                  /  \                                  /  \
                                                                                                                                                                       a    bc            ======>                 bc  a        ======>      cb    a
                                                                                                                                                                             / \                                            /  \                                 / \
                                                                                                                                                                            b   c                                         b    c                              c   b
类似这样的是不能停在中间某一步 必须recursive到底的么？

因为题目不理解清楚也没有办法做  所以希望大家做过的大家能够解答一下疑惑  谢谢了！

1. 左右子树不是只能相差1
2. 可以继续swap子树上的节点

同样的字符集，anagram 要比 scrambled string 多，比如abcde和bdaec是anagram 但不互为scrambled string；另外，可以看看这个：https://oj.leetcode.com/discuss/3632/any-better-solution

stellari 发表于 2015-7-13 20:43
请注意我说的是第二个“答案”，也就是Answers中的第二个。

answered Aug 30, 2014 by dtx0 (960 points)
这个吗？前十几个答案我都扫过了。DP的都是四层循环，写法不一样但是都是O(N^4)，也包括这个。

zhuli19901106 发表于 2015-7-13 20:10
不对啊，那个是递归解法，理论上应该是复杂度应该是O(3^N)，虽然经过剪枝效率也可以很好，但不是多项式级 ...

请注意我说的是第二个“答案”，也就是Answers中的第二个。

真心求解答

楼主知道区别了吗？
我也没看懂有啥区别。

sunnyroom 发表于 2014-7-3 16:12
楼主知道区别了吗？
我也没看懂有啥区别。

没有啊。。。跳过了  搜了好久都没搜到答案

ilnlh 发表于 2014-7-7 04:55
1. 左右子树不是只能相差1
2. 可以继续swap子树上的节点

谢谢解答哈 再追问一下哈 是必须 继续recursively swap到底么

ilnlh 发表于 2014-7-7 04:55
1. 左右子树不是只能相差1
2. 可以继续swap子树上的节点

好的哈 谢谢了  没想到是UCI的学长哈

Lintcode说这题有O(n^3)复杂度解？

zhuli19901106 发表于 2015-7-13 19:40
Lintcode说这题有O(n^3)复杂度解？

O(N^3)的解法就在五楼给出的链接里，第二个答案。

stellari 发表于 2015-7-13 19:57
O(N^3)的解法就在五楼给出的链接里，第二个答案。

不对啊，那个是递归解法，理论上应该是复杂度应该是O(3^N)，虽然经过剪枝效率也可以很好，但不是多项式级的。