亚麻一轮VO

10.16 OA3做完
10.18 OA pass
11.25 VO survey
12.10 VO

烙印，amazon工作5年，上来先相互自我介绍，然后r

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

内容 (2019-12-13 10:10):
12.12 moved to another job

论坛匿名用户 发表于 2019-12-11 10:01
求详细解法

把2个树序列化，再比较一个字符串是否包含另一个字符串。包含的时间复杂度是O(m*n)，用KMP优化可以提高到O(m+n)。

O(max(m,n))是space complexity吧。。时间上的话怎么也不可能比O（m）小啊但是可以用KMP代替java的indexof（）来提升到O（m+n)

BTman 发表于 2019-12-11 17:44
想了下这方法好像行不通，序列化后子树在原树中的位置不是连续的，而且间隔会变，不能简单地变成包含字符 ...

刷题网讨论区有这个解法，把空节点也要序列化，应该没问题吧。

求问楼主 有没有比O（MN）还好的做法？

烟雨秋枫 发表于 2019-12-11 09:23
求问楼主 有没有比O（MN）还好的做法？

有 O(max(m,n)) 的解法，同明天面试

校草哥哥 发表于 2019/12/11 09:37:41
有 O(max(m,n)) 的解法，同明天面试

求详细解法

问楼主 如果unsorted list应该怎么说 直接merge sort吗？

求问一下楼主n-ary tree的思路应该是什么样子的啊？

nyc_underdog 发表于 2019/12/11 10:33:54
问楼主 如果unsorted list应该怎么说 直接merge sort吗？

这个随意，我是转数组再排序，反正复杂度都是nlogn

sundance1 发表于 2019-12-11 11:05
把2个树序列化，再比较一个字符串是否包含另一个字符串。包含的时间复杂度是O(m*n)，用KMP优化可以提高到 ...

想了下这方法好像行不通，序列化后子树在原树中的位置不是连续的，而且间隔会变，不能简单地变成包含字符串问题