Google电面

brian1868 发表于 2019-2-8 05:31
最后时间不到followup没写会有问题吗

我最后挂了 感觉应该是有影响的

Srrrr 发表于 2019-2-10 12:02
我最后挂了 感觉应该是有影响的

我也店面挂了，哎，当时觉得还不错，问的都答出来了，也写出来了。

这followup真的有点难，找到不同字符之后就变成了Shortest Palindrome，那么短的时间还得写个kmp。。。

richpanda 发表于 2019-2-3 04:10
你说的对，我也是这个类似想法，跳到s1相同首字母那，不过这个有o（n）解么？lc 5里面的manacher algorit ...

s1 s2首尾初始匹配之后，s1剩下的往后s2剩下的往前找最长回文，哪个大留哪个。manacher找最长回文是不限制位置的，限制位置感觉更简单了，但一时没想出来O(n)怎么搞。

henryqcy 发表于 2019-2-7 20:37
follow up是有O(n)的解的，关键点是不一样了选A还是B切，然后切在什么地方。
切肯定是以不一样了的那个cha ...

嗯，这样就可以实现O(n)找剩下的最长回文了。总体时间复杂度也就是O(n)