一道脸书电面题

这周面的，还没结果，应该凉凉听口音是天竺朋友，找一个stri

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

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

备下面的面试，谢谢各位同学了

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

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

celiax2y5 发表于 2019/09/22 00:44:39
马拉车是什么算法？

好好刷题吧

暴力吧 把每个字母都去掉一次 然后找回文子串 会马拉车就n方 不会就n立方

补充内容 (2019-9-21 17:22):
如果只是要近似回文子串 围绕每个要删的字符找串就可以 n方就行

lc19890306 发表于 2019/09/22 00:40:23
暴力吧 把每个字母都去掉一次 然后找回文子串 会马拉车就n方 不会就n立方

马拉车是什么算法？

这题和删括号一样。fb高频。

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

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

这题不需要dp，线性时间就可以做出来
Hint：如果是k次delete机会，复杂度为O(n*2^k)

补充内容 (2019-9-23 07:24):
算法是这样，index i和j从两边开始一直往中间走，一直走到第一对s[i] != s[j]的，然后判断s[i:j]和s[i+1:j+1]是不是至少一者是回文的，总时间复杂度是线性的

求问intern or ft

ye8610116 发表于 2019-9-22 17:34
这题不需要dp，线性时间就可以做出来
Hint：如果是k次delete机会，复杂度为O(n*2^k)

可以具体说一下怎么线性时间做么？ 谢谢！