Question：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”]
]
Answer：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
class Solution {
public static List<List<String>>answer;
public static List<String>tmp;
public void search(int idx,String s){
if(tmp.size()>0&&idx>=s.length()){
//List<String> r = (ArrayList<String>)tmp.clone();
answer.add(tmp);
tmp.clear();
}
for(int i=idx;i<s.length();i++){
if(isPalindrome(idx,i,s)){
if(idx==i){
tmp.add(Character.toString(s.charAt(i)));
}else{
tmp.add(s.substring(idx,i+1));
}
search(i+1,s);
tmp.remove(tmp.size()-1);
}
}
}
public boolean isPalindrome(int l,int r,String s){
if(l==r) return true;
while(l<=r){
if(s.charAt(l)!=s.charAt(r))return false;
l++;
r--;
}
return true;
}
public List<List<String>> partition(String s) {
answer=new ArrayList<List<String>>();
tmp=new ArrayList<String>();
search(0,s);
return answer;
}
}
public class Solution {
List<List<String>> resultLst;
ArrayList<String> currLst;
public List<List<String>> partition(String s) {
resultLst = new ArrayList<List<String>>();
currLst = new ArrayList<String>();
backTrack(s,0);
return resultLst;
}
public void backTrack(String s, int l){
if(currLst.size()>0 //the initial str could be palindrome
&& l>=s.length()){
List<String> r = (ArrayList<String>) currLst.clone();
resultLst.add(r);
}
for(int i=l;i<s.length();i++){
if(isPalindrome(s,l,i)){
if(l==i)
currLst.add(Character.toString(s.charAt(i)));
else
currLst.add(s.substring(l,i+1));
backTrack(s,i+1);
currLst.remove(currLst.size()-1);
}
}
}
public boolean isPalindrome(String str, int l, int r){
if(l==r) return true;
while(l<r){
if(str.charAt(l)!=str.charAt(r)) return false;
l++;r--;
}
return true;
}
}
|
近期评论