[leetcode]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"]
  ]

求解所有可能的回文划分。
分析:p=pp(s[1...n])
初始: if n==1, return <<s>>
递归：p=s[1] || pp(s[2...n])
　　　[+s[1..2] || pp(s[3..n]), if s[1..2] is palindrome;
　　　 +s[1..3] || pp(s[4..n]), if s[1..3] is palindrome;
　　　　...
　　　 +s[1..n], if s[1..n] is palindrome;
　　　]
优化：pp(s[i..j])在递归过程中回重复调用，维护Look-up table.
非优化的代码：

View Code

 1 package Palindrome.Partitioning.I;
 2 
 3 import java.util.ArrayList;
 4 
 5 public class calc {
 6 
 7     
 8 
 9     public boolean palindrome(String c) {
10         if(c.length() == 1){
11             return true;
12         }
13         for (int i = 0; i < c.length() / 2; i++) {
14             if (c.charAt(i) != c.charAt(c.length() - 1 - i)) {
15                 return false;
16             }
17         }
18         return true;
19     }
20 
21     public ArrayList<ArrayList<String>> partition(String s) {
22         // Start typing your Java solution below
23         // DO NOT write main() function
24         int sn = s.length();
25         if (sn == 1) {
26             ArrayList<ArrayList<String>> t = new ArrayList<ArrayList<String>>();
27             ArrayList<String> ti = new ArrayList<String>();
28             ti.add(s);
29             t.add(ti);
30             return t;
31         }
32         ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();
33         for (int i = 1; i <= s.length(); i++) {
34             String ss = s.substring(0, i);
35 
36             if (palindrome(ss)) {
37                 if (i == s.length()) {
38                     ArrayList<ArrayList<String>> t = new ArrayList<ArrayList<String>>();
39                     ArrayList<String> ti = new ArrayList<String>();
40                     ti.add(s);
41                     t.add(ti);
42                     ret.addAll(t);
43                 }
44                 ArrayList<ArrayList<String>> t = partition(s.substring(i));
45                 // add ss to head of each array-list
46                 for (ArrayList<String> ti : t) {
47                     ti.add(0, ss);
48                 }
49                 ret.addAll(t);
50 
51             }
52         }
53         return ret;
54     }
55 
56     public static void main(String args[]) {
57         calc c = new calc();
58         ArrayList<ArrayList<String>> t = c.partition("aab");
59         for(ArrayList<String> ti : t){
60             for(String tii : ti){
61                 System.out.print(tii + ", ");
62             }
63             System.out.println();
64         }
65     }
66 
67 }