LinkedIn onsite一道题

原帖地址:mitbbs

给一个string, 可以删除任意字符,求所有可以得到的palidrome字串集

我就想了个递归, 还是没有区分掉一些重复的情况,worst case O(2^n)基本同暴力解
Map> allSubSet = new HashMap();
Set getAllPalidrome(String s, int x, int y){
int ind = x * s.length() + y;
if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
Set ret = new HashSet();
if (s == null || s.size() == 0) { ret.add(“”); return ret;}
if (s.size() == 1) { ret.add(s); return ret;}
for(int i = x; i <= y; i++){ for (int j = y; j >= i; j