谷狗新鲜店面

雨雪霏霏 发表于 2018-11-29 03:37
你好 我认为substring贪心是错误的 比如
str1: abcca
str2: acb

请问这样做对吗

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

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

dengzeyu147 发表于 2018-11-29 04:14
请问这样做对吗
**** 本内容被作者隐藏 ****

line 11是 != 吧？
然后感觉应该是对的~

dengzeyu147 发表于 2018-11-28 15:14
请问这样做对吗
**** 本内容被作者隐藏 ****

感觉唯一的问题就是 如果没有第一问去判断b能否构成a的话
这个代码有可能会死循环

补充内容 (2018-11-28 15:52):
在你的代码中是a能否构成b

yyy884849 发表于 2018-11-29 04:51
感觉唯一的问题就是 如果没有第一问去判断b能否构成a的话
这个代码有可能会死循环

哈哈 这个代码是假设到能构成的情况下，因为楼主给的问题是放一起的， 我忘了把他们放一起了 sry 谢谢

雨雪霏霏 发表于 2018/11/29 03:37:14


你好 我认为substring贪心是错误的 比如
str1: abcca
str2: acb
最优解应该是4 因为str1[0:2]可以由str2的a,b构成
贪心的话只能匹配substr...

有道理诶 如果是subsequence就不可以贪心了

shanshanlate 发表于 2018-11-28 03:59
第二题我是用了iterative的就直接用loop去check那个第一个的substring是不是存在在第二个里面，当时面试 ...

感谢楼主提供思路
请问这样下来为什么是O(n*m)呢
判断一个substring存不存在第二个里面是O(m^2) (不用KMP的话) 然后
是这样判断的吗？
取str1的m长前缀 判断一下
取str1的m-1长前缀 判断一下
..
取str1的1长前缀 判断一下
中间存在就跳出 这就是 O(m^3)
然后判断下一个
总的不就是O(m^3*N)吗

byfwh 发表于 2018-12-10 00:06
感谢楼主提供思路
请问这样下来为什么是O(n*m)呢
判断一个substring存不存在第二个里面是O(m^2) (不用 ...

题目说能够从str2中移走任意数目的字符，也就是说能用来匹配str的不是str2的substring，而是（非连续的）subsequence。方法就是在str当前还未被匹配的部分中，不停地找能够匹配subsequence of str2的最长前缀。在str中找一个能匹配str2子序列的前缀的naive算法需要用时O(m)；最坏情况下，每个匹配部分的长度都为1，也就是说总共要进行O(n)次匹配。所以总时间是O(nm)。

stellari 发表于 2018-12-10 04:00
题目说能够从str2中移走任意数目的字符，也就是说能用来匹配str的不是str2的substring，而是（非连续的） ...

感谢楼主 如果是subsequence的话 的确是这样的
我看还有一个帖子说的follow up是 如果只能取str2的substring

byfwh 发表于 2018-12-10 04:03
感谢楼主 如果是subsequence的话 的确是这样的
我看还有一个帖子说的follow up是 如果只能取str2的subst ...

抱歉，我不是楼主……

如果能用来匹配的一定是str2的substring，而非subsequence的话。那只需要把上面的“str中找一个能匹配str2子序列的最长前缀”这步改成“str中找一个能匹配str2子字符串的最长前缀”即可。于是，寻找一个匹配的时间由O(m)变成了O(m^2)（naive算法）。 因此naive算法情况下总时间应该变为O(nm^2)。