一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1448|回复: 14
收起左侧

[算法题] 求问scramble string和anagram的区别

[复制链接] |试试Instant~ |关注本帖
呵呵君 发表于 2014-6-3 04:32:08 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
最近刷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到底的么?

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

 楼主| 呵呵君 发表于 2014-6-3 09:08:38 | 显示全部楼层
真心求解答
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2014-7-3 16:12:57 | 显示全部楼层
楼主知道区别了吗?
我也没看懂有啥区别。
回复 支持 反对

使用道具 举报

 楼主| 呵呵君 发表于 2014-7-4 07:39:43 | 显示全部楼层
sunnyroom 发表于 2014-7-3 16:12
楼主知道区别了吗?
我也没看懂有啥区别。

没有啊。。。跳过了  搜了好久都没搜到答案
回复 支持 反对

使用道具 举报

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

同样的字符集,anagram 要比 scrambled string 多,比如abcde和bdaec是anagram 但不互为scrambled string;另外,可以看看这个:https://oj.leetcode.com/discuss/3632/any-better-solution
回复 支持 反对

使用道具 举报

 楼主| 呵呵君 发表于 2014-7-10 09:31:48 | 显示全部楼层
ilnlh 发表于 2014-7-7 04:55
1. 左右子树不是只能相差1
2. 可以继续swap子树上的节点

谢谢解答哈 再追问一下哈 是必须 继续recursively swap到底么
回复 支持 反对

使用道具 举报

 楼主| 呵呵君 发表于 2014-7-11 06:50:13 | 显示全部楼层
ilnlh 发表于 2014-7-7 04:55
1. 左右子树不是只能相差1
2. 可以继续swap子树上的节点

好的哈 谢谢了  没想到是UCI的学长哈
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-13 19:40:29 | 显示全部楼层
Lintcode说这题有O(n^3)复杂度解?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-13 19:57:47 | 显示全部楼层
zhuli19901106 发表于 2015-7-13 19:40
Lintcode说这题有O(n^3)复杂度解?

O(N^3)的解法就在五楼给出的链接里,第二个答案。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-13 20:10:24 | 显示全部楼层
stellari 发表于 2015-7-13 19:57
O(N^3)的解法就在五楼给出的链接里,第二个答案。

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

使用道具 举报

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

请注意我说的是第二个“答案”,也就是Answers中的第二个。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-13 21:06:59 | 显示全部楼层
stellari 发表于 2015-7-13 20:43
请注意我说的是第二个“答案”,也就是Answers中的第二个。

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

使用道具 举报

stellari 发表于 2015-7-13 21:15:04 | 显示全部楼层
zhuli19901106 发表于 2015-7-13 21:06
answered Aug 30, 2014 by dtx0 (960 points)
这个吗?前十几个答案我都扫过了。DP的都是四层循环,写法 ...

确实是O(N^4),我少看了一个循环。多谢指出。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-13 21:21:13 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-13 21:45 编辑
stellari 发表于 2015-7-13 21:15
确实是O(N^4),我少看了一个循环。多谢指出。

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

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 00:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表