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"]
]
這個題目考慮用動態(tài)規(guī)劃解題，關鍵在于構造一個解空間，確定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)時間內(nèi)判定任意子串是不是對稱的了。算法實現(xiàn)如下：
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 }