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"]
]
思路：1.推断字符串的字串S.subString(i,j) [i<=j]是否为为回文子串,用boolean型的二维数组
isPalindrome来存储该结果
。在这个地方用了点小技巧，isPalindrome[i]j]会依赖于i
sPalindrome[i+1]j-1] [i+2<=j].
2.如果在求String s的全部回文子串，我们已经知道了s.substring(0,0),s
.substring(0,1),
s.substring(0,2),s
.substring(0,3),
....,s
.substring(0,s.length()-2)的全部回文字串，那我们仅仅须要遍历
i
sPalindrome[i]js.lenth()-1]是不是true｛即从s.substring(i)是不是回文字符串｝若为true，我们取出
s.substring(i-1)的全部回文字串，并在每一种可能性末尾加入
s.substring(i)就可以，代码例如以下
public class Solution {
public boolean[][] isPalindrome(String s) {
boolean[][] isPalindrome = new boolean[s.length()][s.length()];
for (int i = 0; i < s.length(); i++)
isPalindrome[i][i] = true;
for (int i = 0; i < s.length() - 1; i++)
isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
for (int length = 2; length < s.length(); length++) {
for (int start = 0; start + length < s.length(); start++) {
isPalindrome[start][start + length] = isPalindrome[start + 1][start
+ length - 1]
&& s.charAt(start) == s.charAt(start + length);
}
}
return isPalindrome;
}
public List<List<String>> partition(String s) {
boolean[][] isPalindrome= isPalindrome(s);
HashMap<Integer,List<List<String>>> hm=new HashMap<Integer,List<List<String>>>();
for(int i=0;i<s.length();i++){
List<List<String>> ls=new ArrayList<List<String>>();
if(isPalindrome[0][i]){
ArrayList<String> temp=new ArrayList<String>();
temp.add(s.substring(0, i+1));
ls.add(temp);
}
for(int j=1;j<=i;j++){
if(isPalindrome[j][i]){
List<List<String>> l=hm.get(j-1);
List<List<String>> al=new ArrayList<List<String>>();
for(List<String> temp:l){
ArrayList<String> clone=new ArrayList<String>(temp);
clone.add(s.substring(j, i+1));
al.add(clone);
}
ls.addAll(al);
}
}
hm.put(i,ls);
}
return hm.get(s.length()-1);
}
}
