纠结的一道题 返回所有对称子集

如题  
许多年前onsite的一道题，当时挂的心服口服
所以一直纠结，这道题最后到底应该怎么解,才能符合面试官要求?
得到所有的子集,再filter对称的brute force是不可能符合要求的.
抛砖引玉下


补充内容 (2019-9-18 07:38):
return not count Different Palindromic Subsequences
leetcode 730 进阶版，不是统计个数，要得到所有的subsequences

真是道好题啊, 我看也看不懂, 自然是不会做的了

楼主能把题目描述的再详细一点吗

楼主面的L家么…返回所有回文子序列?

lz4321234 发表于 2019-9-18 12:26
楼主面的L家么…返回所有回文子序列?

对的  不过是若干年前面的，突然想到这题了

我一辈子赖美帝 发表于 2019-9-18 12:28
对的  不过是若干年前面的，突然想到这题了

我的想法是 返回所有状态得深搜 但是很多子串会重复搜到 记忆化一下 搞个字典记录一下之前搜到的状态 上来先判断是否搜过当前这个串的所有子串 如果有 就直接返回即可

http://csie.npu.edu.tw/joomla/Seminar/6/C/3.pdf
搜出来一个
先找出所有相同的字符对, 然后k从2到n/2做 k-1组字符对 和 1组字符对 匹配, 要求下标在外面
> Obviously, the time complexity of this sample algorithm is O(n3)

但我觉得这是n^2 2^n的...

或者DFS存 前缀 和 下标 爆搜

Airtnp 发表于 2019-9-19 22:35
http://csie.npu.edu.tw/joomla/Seminar/6/C/3.pdf
搜出来一个
先找出所有相同的字符对, 然后k从2到n/2做 ...

sorry no chinese input


I asked the interviewer after the linkeded in onsite, the guy said O(n3) is correct answer

我一辈子赖美帝 发表于 2019-9-19 22:43
sorry no chinese input

平均情况下可能是的
但是对于aaaaaaaaaaaaa这个就是n^2 2^n了啊

我也想了好久，重点在于如何避免重复。我的想法核心按目标串顺序找，用上DP。比如先找a,b,c,d, 再找aa, bb, cc, dd，再找aaa, aba, aca, ada.... 按这个顺序来
这个情况就可以变成先从两侧找俩a，再从俩a之间找所有的sebsuquence，找俩b，找俩b之间所有的subsequence，以此类推。
用上memorization以后，复杂度三次方