Facebook Intern 二面

hanchen999 · 2015-10-11 02:52:17

弄个set装起来就行，然后把str2的所有长度为n的substr遍历一下

kennynoodlehous · 2015-10-11 03:33:29

hanchen999 发表于 2015-10-11 02:52
弄个set装起来就行，然后把str2的所有长度为n的substr遍历一下

谢谢您，刚才和人讨论了一下，貌似这题有可能用DP做也行，我想想

hanchen999 · 2015-10-11 03:45:41

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

潇洒走一回 · 2015-10-11 04:55:55

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

mileschen2008 · 2015-10-11 11:53:37

hanchen999 发表于 2015-10-11 03:45
DP确实可行，当时觉得这是第一题，就没往那个方向想。不dp我觉得复杂度应该是N*str.length(), dp估计能降到 ...

Set的复杂度应该是len1^3 + len^3吧，应该需要求N, N+1...len1长度的substring.

huoshankou

第一题还是不太明白。他要求N 或者 N以上的。你的set只装长度为N的子串？那长度为N + 1， N + 2， N + 3, ...呢？

yjfox

longest common substring
大伙为啥这么纠结

Augustus

huoshankou 发表于 2015-12-1 12:24
第一题还是不太明白。他要求N 或者 N以上的。你的set只装长度为N的子串？那长度为N + 1， N + 2， N + 3, . ...

同不明白，求解释

hanchen999

N + 1以上包含N，就是比如规定长度是2，两个字符串都包含abc，在发现abc之前你就会看见ab然后直接返回false...

huoshankou

hanchen999 发表于 2015-12-3 05:35
N + 1以上包含N，就是比如规定长度是2，两个字符串都包含abc，在发现abc之前你就会看见ab然后直接返回fa ...

所以这个题只是返回能不能找到，不是让你返回所有的长度大于等于N的共同子串喽。