Palindrome Partitioning

Palindrome Partitioning

 

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ] 

Naive Way:第一感觉可以用recursive的方法，对String第一个palindrome及它后面的部分

分别进行recursive call求palindrome partition。具体下来就是：

如果一个String只有一个字符，则返回单个字符的list。

否则，遍历String,一旦遇到palindrome就提取该子串作为头，对后部分分别进行recursive call，

合并两者，加入结果中。 

有一个问题就是如何求包含第一个字母的所有palindrome。在longest palindrome substring中

在O(n)内可以求出以所有字符为中心最大范围的palindrome,当然用在这里肯定也可以求处包含第一个

字符的所有palindrome。当肯定不是最佳的，但是要想找出在小于O(n)的时间内求出包含第一个字符

的所有palindrome，看来是不可能的，所以，干脆就用这个方法了。

这里我用求longest palindrome substring中的方法求出所有包含第一个字符的palindrome的

最后位置，以此方便分割字符。

算法复杂度应该是f(n)+f(n-1)+f(n-2)+... 而f(n)在最坏的情况应该是O(2^n)的，所以最后的

算法复杂度是O(2^n)。不知道这样算对不对，总之是一个很差的算法复杂度。

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> gross = new ArrayList<List<String>>();
        List<Integer> num = panlindromeIndex(s);
        for(int i = 0;i < num.size();i++){
            String left = s.substring(0,num.get(i));
            List<List<String>> right = partition(s.substring(num.get(i),s.length()));
            if(right.size()==0){
                List<String> base = new ArrayList<String>();
                base.add(left);
                gross.add(base);
            }
            for(int j = 0;j < right.size();j++){
                right.get(j).add(0,left);
                gross.add(right.get(j));
            }
        }
        return gross;
    }
    
    // return a list of position(i) where [0~i] is a panlindrome
    private List<Integer> panlindromeIndex(String s){
        List<Integer> list = new ArrayList<Integer>();
        s = preProcess(s);
        int p = 0;
        int f[] = new int[s.length()];
        for(int i = 1;i < s.length();i++){
            f[i] = 1;
            if(i < p + f[p]){
                if(p+f[p] - i > f[2*p-i])
                    f[i] = f[2*p-i];
                else
                    f[i] = p+f[p]-i;
            }
            while(i-f[i] >= 0 && i + f[i] < s.length()){
                if(s.charAt(i-f[i])!=s.charAt(i+f[i]))
                    break;
                f[i]++;
            }

            if(i+f[i] > p+f[p]){p=i;}

        }
        for(int i = 1;i < f.length;i+=2){
            if(i-f[i] < 0)
                list.add((i+f[i])/2);
            if(i-1-f[i-1] < 0)
                list.add((i-1+f[i-1])/2);
        }
        return list;
    }
    
    private String preProcess(String s){
        StringBuilder rlst = new StringBuilder();
        for(int i = 0;i < s.length();i++){
            rlst.append('#');
            rlst.append(s.charAt(i));
            if(i==s.length()-1)
                rlst.append('#');
        }
        return rlst.toString();
    }
}

Improved Way:为了提高算法效率，我思考了一下以上算法的缺陷。recursive call里产生

的子字符串很多都是重复的，这里使算法效率降低了很多。有没有办法先把这些有效的子字符串

写好，然后需要的时候直接调用呢？这时我想到了求longest palindrome substring最

原始的方法——DP。DP可以用一个二维矩阵告诉我某一段子字符串是否回文，着就相当于把所有

可能的子字符串都先求出来了，那如何调用呢。DP得到的是一个二维矩阵，通过上一层的某段

是否回文，可以用DFS的方法，遍历下一层对应所有可能的回文子串，这里又是用带回溯的DFS，

就像N-Queen和Sudoku一样。

算法复杂度为O(n^2)。比之前提高了不少。

public class Solution {
    public List<List<String>> partition(String s) {
        // DP
        List<List<String>> gross = new ArrayList<List<String>>();
        Deque<Range> deque = new LinkedList<Range>();
        Stack<Range> stack = new Stack<Range>();
        boolean opt[][] = new boolean[s.length()][s.length()+1];
        // base case
        for(int i = 0;i < s.length();i++){
            opt[i][i+1] = true;
            opt[i][i] = true;
        }
        // iteration
        for(int i = 2;i <= s.length();i++)
            for(int j = 0;j+i <= s.length();j++)
                opt[j][j+i] = s.charAt(j)==s.charAt(j+i-1) && opt[j+1][j+i-1];
        // construct result using DFS
        for(int i = 1;i <= s.length();i++){
            if(opt[0][i]){
                Range range = new Range(0,i);
                stack.push(range);
            }
        }
        while(!stack.isEmpty()){
            Range range = stack.pop();
            deque.offerLast(range);
            boolean hasNext = false;
            if(range.e==s.length()){
                List<String> list = new ArrayList<String>();
                for(int i = 0;i < deque.size();i++){
                    Range next = deque.pollFirst();
                    list.add(s.substring(next.b,next.e));
                    deque.offerLast(next);
                }
                gross.add(list);
            }else{
                for(int i = range.e+1;i <= s.length();i++){
                    if(opt[range.e][i]){
                        Range sub = new Range(range.e,i);
                        stack.push(sub);
                        hasNext = true;
                    }
                }
            }
            // back trace
            if(!hasNext || range.e==s.length()){
                if(!stack.isEmpty()){
                    Range peek = stack.peek();
                    while(!deque.isEmpty()){
                        if(deque.pollLast().b == peek.b)
                            break;
                    }
                }
            }
        }
        return gross;
    }
    

    class Range{
        int b;
        int e;
        Range(int begin, int end){
            b = begin;
            e = end;
        }
    }
} 

看了看自己第一次的做法，发现比这种用DFS遍历的方法高明多了，是根据DP的二维矩阵从后往前

进行遍历的方法。运行时间也是最短的。

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> lst = new ArrayList<List<String>>();
        List<String> temp = new ArrayList<String>();
        int len = s.length();
        boolean opt[][] = new boolean[len][len];
        
        // initialize
        for(int i = 0;i < len;i++){Arrays.fill(opt[i], false);}
        for(int i = 0;i < len;i++){opt[i][i] = true;}
        
        // recurrence
        for(int u = 1;u < len;u++){
         for(int i = 0;i+u < len;i++){
          if(u >= 2){
           opt[i][i+u] = (opt[i+1][i+u-1] && s.charAt(i)==s.charAt(i+u));
          }else if(u == 1){
           opt[i][i+u] = s.charAt(i) == s.charAt(i+u)? true:false;
          }
         }
        }
        
        // generate result according to opt
        generateList(0,len,s,opt,temp,lst);

        //show result
        //System.out.print(lst);
        return lst;

    }

 

 private boolean generateList(int i, int len, String s, boolean opt[][], List<String> temp,List<List<String>> lst){
  for(int j = 0;j < len; j ++){
   if(opt[i][j]){
    List<String> newCombo = new ArrayList<String>(temp);
    newCombo.add(s.substring(i, j+1));
    if(j == len-1){
     lst.add(newCombo);
    }else{
     generateList(j+1,len,s,opt,newCombo,lst);
    }
   }
  }
  return true;
 }

} 

突然发现我的算法课老师Michael讲的如何回溯DP得到的矩阵，得到正式的结果的那种从尾到头的方法，其实是一种DFS。