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"]
]
这个题目考虑用动态规划解题，关键在于构造一个解空间，确定S的任意子串S(i, j)是不是对称的。判断标准如下：
1、如果i == j，则S(i, j)是对称的；
2、如果j - i == 1 && S[i] == S[j]，则S(i, j)是对称的；
3、如果j - i > 1 && S[i] == S[j] && S(i + 1, j - 1)是对称的，则S(i, j)也是对称的。
在构造完这样的解空间后，就可以在O(1)时间内判定任意子串是不是对称的了。算法实现如下：
1 public class PalindromePartitioning {
2 public ArrayList<ArrayList<String>> partition(String s) {
3 ArrayList<ArrayList<String>> ret =
new ArrayList<ArrayList<String>>();
4 ArrayList<String> r =
new ArrayList<String>();
5 int length = s.length();
6 boolean[][] map =
new boolean[length][length];
7 findPartition(s, 0, ret, r, map);
8 return ret;
9 }
10 11 private void findPartition(String s,
int start,
12 ArrayList<ArrayList<String>> ret, ArrayList<String> r,
13 boolean[][] map) {
14 int length = s.length();
15 if (start == length && r.size() != 0) {
16 ArrayList<String> clone =
new ArrayList<String>(r);
17 ret.add(clone);
18 }
else {
19 for (
int j = start; j < length; j++) {
20 if (start == j
21 || (j - start > 1 && s.charAt(start) == s.charAt(j) && map[start + 1][j - 1])
22 || (j - start == 1 && s.charAt(start) == s.charAt(j))) {
23 map[start][j] =
true;
24 r.add(s.substring(start, j + 1));
25 findPartition(s, j + 1, ret, r, map);
26 r.remove(r.size() - 1);
27 }
28 }
29 }
30 }
31 }