find all possible subsequence palindrome for given string

45分钟电面，上来先介绍工作经历，聊了聊工作中遇到的难题及应对策略，然后面试官介绍了一下uber的情况，尤其是他们组的情况。然后开始在coderpad.io上答题：
find all possible subsequence palindro

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

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

官表示每周工作50h，仍在平均水平一下，果然是很忙。

已跪，后来人记得刷刷这题啊！

附上相关paper一篇，供参考：

居然会问这种题...我还是缴械投降吧  TAT

用一个hashtable，记录每个char出现次数，然后用类似permutation办法，可以么？

感觉应该是暴力搜索啊

dylanoo 发表于 2015-10-29 23:06
用一个hashtable，记录每个char出现次数，然后用类似permutation办法，可以么？

要保持char的顺序啊

感觉需要通过改动LCS的那个dp矩阵来做，但是不太确定。

我擦，暴力豆不会解，比leetcode那道难呐

likenisha 发表于 2015-11-11 02:13
我擦，暴力豆不会解，比leetcode那道难呐

暴力就是 组合所有的words,combination.
然后看谁是palindrome。

补充内容 (2015-11-11 02:52):
好像发现，我没有理解题

噢，我知道了，这个题暴力法就是subset，看所有subset哪个是palindrome，但是dp应该怎么想，求大神指教

1. public class test{
   
2. 
   
3.         public static void main(String[] args){
   
4.                 System.out.print(test.findsequence("cdc"));
   
5.         }
   
6. 
   
7.          static List<String> findsequence(String s){
   
8.                  int index = 0;
   
9.                  StringBuffer path = new StringBuffer();
   
10.                  Set<String> ret = new HashSet<String>();
    
11.                  helper(s,ret,path,index);
    
12.                  return new ArrayList<String>(ret);
    
13.          }
    
14.          static void helper(String s, Set<String>ret, StringBuffer path, int index){
    
15.                  if(path.length() != 0 && isValid(path) && !ret.contains(path.toString())){
    
16.                          ret.add(path.toString());
    
17.                  }
    
18.                  
    
19.                  for(int i = index; i < s.length(); i++){
    
20.                          char c = s.charAt(i);
    
21.                          path.append(c);
    
22.                          helper(s,ret,path,i + 1);
    
23.                          path.deleteCharAt(path.length() - 1);
    
24.                  }
    
25.          }
    
26.          static boolean isValid(StringBuffer s){
    
27.                  int left = 0;
    
28.                  int right= s.length() - 1;
    
29.                  while(left < right){
    
30.                          if(s.charAt(left) != s.charAt(right)) return false;
    
31.                          left++;
    
32.                          right--;
    
33.                  }
    
34.                  return true;
    
35.          }
    
36. }

复制代码

写了一个dfs版本的， dp实在是想不出来