Google电面

Srrrr 发表于 2019/02/03 03:50:12


嗯 和我当时说的差不多 但是followup里其实不需要s1的指针跳到s2 比如
“ABCDCF”  
“ZZZZBA”

s1 指针在2， s2指针在3
就直接s1开始找以2为首最长的...

你说的对，我也是这个类似想法，跳到s1相同首字母那，不过这个有o（n）解么？lc 5里面的manacher algorithm可以搞定不？

masunshi 发表于 2019-2-3 04:02
祝好运

嗯嗯 多谢！ same to you！

如何用manacher algorithm？

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

manacher 我觉得应该可以吧 但是估计要做点修改 毕竟这里他首或者尾是固定的

谢谢分享 正在准备面试

用two pointer，如果当前字母不同就切割，在不同字母之前切还是之后切？ 还是之前切一刀之后也切一刀试试呢？
因为有字符相同就不切， 如果两个字符串比较的时候，相同不同字符间隔出现，可能因为字符相同不切而漏掉解答。
感觉，一旦出现不同字符，可能就需要暴力切割来避免漏掉的问题。

漫漫人生路 发表于 2019-2-3 09:17
用two pointer，如果当前字母不同就切割，在不同字母之前切还是之后切？ 还是之前切一刀之后也切一刀试试呢 ...

实在没看懂这个edge case 能给个例子嘛
切一定是在不同字母之前切 之后切的话 岂不是俩不匹配的字符被收录进去了 那肯定不是parlindrom了

Srrrr 发表于 2019-2-3 09:34
实在没看懂这个edge case 能给个例子嘛
切一定是在不同字母之前切 之后切的话 岂不是俩不匹配的字符被 ...

嗯，不同字母之前切，不过，需要s1， s2跟s2， s1都试一遍。

请问下楼主怎么准备狗家的电面呢，我大概还有一周的时间，无从下手

漫漫人生路 发表于 2019-2-3 09:46
嗯，不同字母之前切，不过，需要s1， s2跟s2， s1都试一遍。

对的 是得要镜像都来一次