黑车店面

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

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

find all palindrome subsequences
linkedlin 专门用这题来挂人的
面试如果碰到这题，说明面官摆明了坑你的
这题dp无效
要用到双向DFS
要创建node{char c, int idx}
3个map, 一个记录char映射，一个记录idx和char的映射，一个记录idx和node的映射
时间复杂度度最优可以到O3

如果是所有的，而不是个数，dp没啥用的，就是最基础的暴力破解。dp的话可以记录 i - j 之间出现的回文，那么 i - 1和 j + 1一样就可以用中间的回文进行排列组合。但有要求所有未重复的，比如说abbaabba，abba显然重复两次了，还要走HashSet做验证，所以其实dp没啥用，只能暴力解

看上去用backtrack可以？

有比暴力解更好的优化的，从中间往两边发散，worst case time complexity不变但是avg可以好很多因为可以提前剪枝

求个楼主后续~

感觉可以当成蠡口 耳流器 的变种去做。

jsunderland 发表于 2020-12-3 16:54
感觉可以当成蠡口 耳流器 的变种去做。

应该可以。耳流器只需要记录每个char的个数，这个还得记录位置，因为subsequence的相对位置不能变。不知道有没有更好的解法

居然有paper专门讲这个
Finding all Palindrome Subsequences in a Stringhttps://citeseerx.ist.psu.edu/vi ... p=rep1&type=pdf

牛批，这要是没见过这题，还得在不到一小时的时间里面把论文的想法都给整出来，残暴。