Google电面

今天下午面的Google 全职电面 面试官感觉像个国人大哥 挺nice的 题也不难 但是一开始想复杂了

给两个长度一样的string A，B  把他们对齐切一刀 这样就得到了A1 A2 B1 B2 四个substring
写一个func check 能不能找到这一刀  A1和B2 拼起来

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

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

的时候把速度放慢了点 顺带着解释 虽然也没啥好解释的 就尽量interact 所以后面没啥时间 followup时候就讲了idea怎么实现 没具体写code了 希望能给个旅游的机会吧

这道题考双指针的灵活用法。先只考虑a1b2的情况（另外那种情况a2b1是对称的，互换一下s1和s2就可以了。）双指针，一个指向s1的左边，一个s2的右边，同时扫，如果字母不同，就考虑切割，切割完有两种可能路径，可以选择s2那个指针跳到s1去，也可以反过来。这两种路径只要一个能走通就返回true，否则false。follow up比较类似，不过现在有两次切割机会。当字母不同时用掉第一次切割，s2那个指针跳到s1去，或者反过来也可以。这时候问题变成了找两个指针指向的这段substring中包含首（尾）字母最长palindrome的问题了。这个问题应该有o（n）解吧？高手讲解一下？

follow up是有O(n)的解的，关键点是不一样了选A还是B切，然后切在什么地方。
切肯定是以不一样了的那个char开始的在长的回文除，而找longest prefix parlindrome可以先flip string，然后用KMP找longest identical suffix，因为回文flip以后和原本的回文还是一样的。参考里扣214

follow up 用 马拉车 来处理剩下的字符串。
比如 A 切在 index 3, 我们对A[3]之后的跑马拉车，然后马拉车中，遍历每个中心，遇到每个中心对应的回文半径能覆盖到A[4]的, 则证明这是从A[4]开始的最长回文，更新最长回文。
对B也做一遍，比较两个最长回文然后判断怎么切。

Follow up是枚举所有切法，然后选出最长的palindrome ?

对其切的话怎么样用two pointer呢？ 难道不需要枚举所有的切法吗 求提示

wtcupup 发表于 2019-2-2 15:32
Follow up是枚举所有切法，然后选出最长的palindrome ?

就是如果A B的切口可以不在同一个地方 然后找拼出来的最长的palindrome 我当时给的解法也是双指针 感觉不需要枚举呀

hongjiw 发表于 2019-2-2 15:54
对其切的话怎么样用two pointer呢？ 难道不需要枚举所有的切法吗 求提示

楼下有个大哥的解释 和我当时想的差不多 就主要是因为这个新生成的palindrome 如果存在的话 他的头和尾一定一个来自A的头(尾)， 一个来自B的头(尾) 所以双指针指向A B的两端 然后往中间扫

cheerier 发表于 2019-2-3 00:42
不对齐切的话，l 从A的左边开始，r从B的右边开始 然后一起扫？ 如果l和r对应的char相同则继续，不相同就是 ...

不相同的话 就必须切了 但是切A 还是切B 此时还是不一定的 比如  “ABCDCF”  “ZZZZBA”  这样“AB” “BA”之后就肯定需要选一个String切一刀了 其实可以发现 String A 还可以往后 因为“CDC” 是个 parlindrome 所以String A 可以等到C之后在切  同理 String B 也可以往后 “ZZZZ” 也是个parlindrome 这时候 两者相比我们取长的 就是“ZZZZ” 这样新组的parlindrome 就是 “ABZZZZBA” 就肯定最长了 我当时是这么说的 不知道会不会有啥edge case

richpanda 发表于 2019-2-3 02:57
这道题考双指针的灵活用法。先只考虑a1b2的情况（另外那种情况a2b1是对称的，互换一下s1和s2就可以了。）双 ...

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

s1 指针在2， s2指针在3
就直接s1开始找以2为首最长的parlindrome
s2开始找以3为尾最长的parlindrome
然后比下俩parlindrome的长度就成了

祝好运