Massive Algorithms: Get all palidromes after delete

Get all palidromes after delete - Linkedin

给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
http://www.mitbbs.com/article_t/JobHunting/33053715.html
private static ISet<string> getPal(string s){
IDictionary<char, IList<int>> dict = new Dictionary<char, IList<int>>();
for(int i = 0; i < s.Length; i++){
    if(!dict.ContainsKey(s[i])) dict[s[i]] = new List<int>();
    dict[s[i]].Add(i);
}
ISet<string> result = new HashSet<string>();
dfs(result, new StringBuilder(), new StringBuilder(), s, 0, s.Length - 1,
dict);
return result;
}
private static void dfs(ISet<string> result, StringBuilder sLeft,
StringBuilder sRight, string s, int left, int right, IDictionary<char, IList
<int>> dict){
for(int i = left; i <= right; i++){
    result.Add(sLeft.ToString() + s[i] + sRight.ToString());
    for(int j = 0; j < dict[s[i]].Count; j++)
      if(dict[s[i]][j] <= i) continue;
      else if (dict[s[i]][j] > right) break;
      else{
        sLeft.Append(s[i]);
        sRight.Insert(0, s[i]);
        result.Add(sLeft.ToString() + sRight.ToString());
        dfs(result, sLeft, sRight, s, i + 1, dict[s[i]][j] - 1, dict);
        sLeft.Length -= 1;
        sRight.Remove(0, 1);
        dfs(result, sLeft, sRight, s, i + 1, dict[s[i]][j] - 1, dict);
      }
}
}

function reverse(s) {
    var o = '';
    for (var i = s.length - 1; i >= 0; i--)
        o += s[i];
    return o;
};

var p = function(s) {
    var prevLookup = {};
    var nextLookup = {};

    for (var i = 0; i < s.length; i++) {
        var c = s.charAt(i);
        if (!prevLookup[c]) {
            prevLookup[c] = [];
            nextLookup[c] = [];
        }
    }

    for (var i = 0; i < s.length; i++) {
        for(var c in prevLookup) {
            var lookup = prevLookup[c];
            if (c == s.charAt(i)) {
                lookup[i] = i;
            } else {
                if (i == 0) {
                    lookup[i] = null;
                } else {
                    lookup[i] = lookup[i-1];
                }
            }
        }
    }

    for (var i = s.length-1; i >= 0; i--) {
        for(var c in nextLookup) {
            var lookup = nextLookup[c];
            if (c == s.charAt(i)) {
                lookup[i] = i;
            } else {
                if (i == s.length-1) {
                    lookup[i] = null;
                } else {
                    lookup[i] = lookup[i+1];
                }
            }
        }
    }

    console.log(prevLookup);
    console.log(nextLookup);

    var _rec = function(left, right, accum) {
        console.log(accum + reverse(accum));
        if (left > right) return;

        for (var c in prevLookup) {
            var leftMostPos = nextLookup[c][left];
            var rightMostPos = prevLookup[c][right];
            if (leftMostPos != null && leftMostPos <= right) {
                console.log(accum + c + reverse(accum));
                if (rightMostPos > leftMostPos) {
                    _rec(leftMostPos + 1, rightMostPos -1, accum + c);
                }
            }
        }
    };

    _rec(0, s.length-1, "");
};

var s = "abcbabcba";
var s2 = "aaaaaaaa";
无重复的逐一完全遍历所有的substring
palindrome。复杂度就是O(the number of palindrome substrings).
blaze 的解法很巧妙。关键是建立两个不同方向的lookup table,每个entry分别是字符
以及一个数组，数组中的 i 元素是从 i 位置往左（右）看能看到的该字符的最近位
置。然后从两边向中间扫描。

关于leetcode 266， 267 参考：

http://buttercola.blogspot.com/2015/08/leetcode-palindrome-perm
very nice solution
关键是对每个可能的char，维护了一维数组，数组中的i意思是从这个i看过去下一个
same char出现的位置，这样DFS就是对char来做遍历。
而且这个解法很巧妙的解决了奇数长和偶数长的问题。
我的java实现，参考了Blaze的思路，不过不知道真正理解了他的思路没有，因为我不
太看得懂javascript.下面是几个点：

1. 这个题目用的是backtracking而不是dp，因为dp不可能给你产生排列组合。dp通常
就是给你一个最值。
2. 时间复杂度是指数级。
3. 题目的本质是产生排列。
4. 一般的backtracking来形成字符串的话,从现有字母集中每次任意挑一个字母,然后
从剩下的字母里继续挑。把所有字母都加到字符串里面去了，这轮程序也就完了。这个
题目因为有个顺序的限制条件，决定程序怎样进行下去并不能用剩下多少字符来决定，
而应该是用已经加入字符串的字母的位置来决定。

import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Set;

public class Example5 {
    public static void main(String [] args){
        Example5 o = new Example5();
        List <String> results = o.setUp("abcbabcba");
        for(String str: results){
            System.out.println(str);
        }
    }
    public List <String> setUp(String palidrome){
        HashMap <Character, List<Integer>> map = new HashMap <Character,
List<Integer>>();
        HashMap <Character, Pointers> locations = new HashMap <Character,
Pointers>();
        char [] chs = palidrome.toCharArray();
        int i = 0;
        for(i=0;i<chs.length;i++){
            if(map.containsKey(chs[i])){
                map.get(chs[i]).add(i);
            }
            else{
                List <Integer> tmp = new ArrayList <Integer> ();
                tmp.add(i);
                map.put(chs[i],tmp);
            }
        }
        Set <Character> keySet = map.keySet();
        Iterator <Character> iter = keySet.iterator();
        List <String > results = new ArrayList <String> ();
        while(iter.hasNext()){
            Character ch=iter.next();
            //results.add(ch.toString());
            int size = map.get(ch).size();
            locations.put(ch, new Pointers(0,size-1));
        }
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        dfs(results,0,chs.length-1,sb1,sb2,keySet,map,locations);
        return results;
    }

    private class Pointers {
        int left;
        int right;
        public Pointers(int left, int right){
            this.left = left;
            this.right = right;
        }
    }

    public void dfs (List <String> results, int left, int right,
StringBuilder sb1, StringBuilder sb2, Set <Character> keySet, HashMap <
Character, List<Integer>> map, HashMap <Character, Pointers> locations) {
        Iterator <Character> iter = keySet.iterator();
        while(iter.hasNext()){
            Character ch=iter.next();
            //System.out.println("ch="+ch+" left="+left+" right="+right);
            Pointers p=locations.get(ch);
            //System.out.println("left1="+p.left+" right1="+p.right);
            List <Integer> nums = map.get(ch);
            int oldLeft = p.left;
            int oldRight = p.right;
            while((p.left<=p.right)&&(nums.get(p.left)<left)){
                p.left++;
            }
            while((p.left<=p.right)&&(nums.get(p.right)>right)){
                p.right--;
            }
            if(p.left<=p.right){
                results.add(sb1.toString()+ch+sb2.toString());
                //System.out.println(sb1.toString()+ch+sb2.toString());
            }
            if(p.left<p.right){
                sb1.append(ch);
                sb2.insert(0,ch);
                int tmp1 = p.left;
                int tmp2 = p.right;
                p.left++;
                p.right--;
                //System.out.println(sb1.toString()+sb2.toString());
                results.add(sb1.toString()+sb2.toString());
                dfs(results,nums.get(tmp1)+1,nums.get(tmp2)-1,sb1,sb2,keySet
,map,locations);
                sb1.deleteCharAt(sb1.length()-1);
                sb2.deleteCharAt(0);
            }
            p.left = oldLeft;
            p.right = oldRight;
        }
    }
}
这所有的回文字串有点难啊，我把mitbbs上的解法翻译成C++了

#include <vector>
#include <iostream>
#include <string>
#include <map>
using namespace std;

map<char, vector<int>> leftbook;
map<char, vector<int>> rightbook;

void fill(string s) {
for (auto x : s) {
      if (leftbook.find(x) == leftbook.end())
         leftbook[x] = vector<int>(s.size(), -1);
      if (rightbook.find(x) == rightbook.end())
         rightbook[x] = vector<int>(s.size(), -1);
}

for (int i = 0; i < s.size(); ++i) {
      for (auto p = leftbook.begin(); p != leftbook.end(); ++p) {
         if (s == p->first)
            (p->second) = i;
         else 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
            (p->second) = (i == 0 ? -1 : (p->second)[i-1]);
      }.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
}. From 1point 3acres bbs

for (int i = s.size() - 1; i >= 0; --i) {
      for (auto p = rightbook.begin(); p != rightbook.end(); ++p) {
         if (s == p->first). more info on 1point3acres.com
            (p->second) = i;
         else
            (p->second) = (i == s.size() - 1 ? -1 : (p->second)[i+1]);
      }
}

}
-google 1point3acres
void fun(int l, int r, string half) {
cout<<half + string(half.rbegin(), half.rend())<<endl;
for (auto p = leftbook.begin(); p != leftbook.end(); ++p) {.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
      char c = p->first;
      int left = rightbook[c][l];
      int right = leftbook[c][r];
      if (left != -1 && left <= r) {.鏈枃鍘熷垱鑷�1point3acres璁哄潧
         cout<<half + c + string(half.rbegin(), half.rend())<<endl;
         if (right > left)
            fun(left + 1, right - 1, half + c);
      }
}.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
}. visit 1point3acres.com for more.
鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
int main(int argc, char const *argv[])
{
string s = "abcba";
fill(s);
fun(0, s.size() - 1, "");
return 0;. from: 1point3acres.com/bbs
}
补充内容 (2015-11-6 11:29):
leftbook是每个字符往左能看到的位置，rightbook是每个字符往右能看到的位置。
算法就是对所有的字符遍历并拼接起来。拼接的条件是，下一个字符必须落在上一个字符的两个book所规定的范围里

Get all palidromes after delete - Linkedin

Labels

Popular Posts