求问scramble string和anagram的区别

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

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

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

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

zhuli19901106 发表于 2015-7-13 21:06
answered Aug 30, 2014 by dtx0 (960 points)
这个吗？前十几个答案我都扫过了。DP的都是四层循环，写法 ...

确实是O(N^4)，我少看了一个循环。多谢指出。

stellari 发表于 2015-7-13 21:15
确实是O(N^4)，我少看了一个循环。多谢指出。

O(n^4)的解很直观，我已经写了。在想是不是有类似四边形不等式之类的方法，我试试看吧。
无解。。看来暂时搞不出来。。