|
3 | 3 | importjava.util.ArrayList; |
4 | 4 | importjava.util.List; |
5 | 5 |
|
6 | | -/** |
7 | | - * 131. Palindrome Partitioning |
8 | | -
|
9 | | - Given a string s, partition s such that every substring of the partition is a palindrome. |
10 | | -
|
11 | | - Return all possible palindrome partitioning of s. |
12 | | -
|
13 | | - For example, given s = "aab", |
14 | | - Return |
15 | | -
|
16 | | - [ |
17 | | - ["aa","b"], |
18 | | - ["a","a","b"] |
19 | | - ] |
20 | | -
|
21 | | - */ |
22 | 6 | publicclass_131 { |
23 | 7 |
|
24 | | -publicstaticclassSolution1 { |
25 | | -publicList<List<String>>partition(Strings) { |
26 | | -List<List<String>>result =newArrayList(); |
27 | | -intn =s.length(); |
28 | | -boolean[][]dp =newboolean[n][n]; |
29 | | -for (inti =0;i <n;i++) { |
30 | | -for (intj =0;j <=i;j++) { |
31 | | -if (s.charAt(j) ==s.charAt(i) && (j +1 >=i -1 ||dp[j +1][i -1])) { |
32 | | -// j+1 >= i-1 means j and i are adjance to each other or only one char apart from each other |
33 | | -//dp[j+1][i-1] means its inner substring is a palindrome, so as long as s.charAt(j) == s.charAt(i), then dp[j][i] must be a palindrome. |
34 | | -dp[j][i] =true; |
35 | | - } |
| 8 | +publicstaticclassSolution1 { |
| 9 | +publicList<List<String>>partition(Strings) { |
| 10 | +List<List<String>>result =newArrayList(); |
| 11 | +intn =s.length(); |
| 12 | +boolean[][]dp =newboolean[n][n]; |
| 13 | +for (inti =0;i <n;i++) { |
| 14 | +for (intj =0;j <=i;j++) { |
| 15 | +if (s.charAt(j) ==s.charAt(i) && (j +1 >=i -1 ||dp[j +1][i -1])) { |
| 16 | +// j+1 >= i-1 means j and i are adjance to each other or only one char apart from each other |
| 17 | +//dp[j+1][i-1] means its inner substring is a palindrome, so as long as s.charAt(j) == s.charAt(i), then dp[j][i] must be a palindrome. |
| 18 | +dp[j][i] =true; |
| 19 | + } |
| 20 | + } |
| 21 | + } |
| 22 | + |
| 23 | +for (boolean[]list :dp) { |
| 24 | +for (booleanb :list) { |
| 25 | +System.out.print(b +", "); |
| 26 | + } |
| 27 | +System.out.println(); |
| 28 | + } |
| 29 | +System.out.println(); |
| 30 | + |
| 31 | +backtracking(s,0,dp,newArrayList(),result); |
| 32 | + |
| 33 | +returnresult; |
36 | 34 | } |
37 | | - } |
38 | | - |
39 | | -for (boolean[]list :dp) { |
40 | | -for (booleanb :list) { |
41 | | -System.out.print(b +", "); |
42 | | - } |
43 | | -System.out.println(); |
44 | | - } |
45 | | -System.out.println(); |
46 | | - |
47 | | -backtracking(s,0,dp,newArrayList(),result); |
48 | | - |
49 | | -returnresult; |
50 | | - } |
51 | 35 |
|
52 | | -voidbacktracking(Strings,intstart,boolean[][]dp,List<String>temp, |
53 | | -List<List<String>>result) { |
54 | | -if (start ==s.length()) { |
55 | | -List<String>newTemp =newArrayList(temp); |
56 | | -result.add(newTemp); |
57 | | - } |
58 | | -for (inti =start;i <s.length();i++) { |
59 | | -if (dp[start][i]) { |
60 | | -temp.add(s.substring(start,i +1)); |
61 | | -backtracking(s,i +1,dp,temp,result); |
62 | | -temp.remove(temp.size() -1); |
| 36 | +voidbacktracking(Strings,intstart,boolean[][]dp,List<String>temp, |
| 37 | +List<List<String>>result) { |
| 38 | +if (start ==s.length()) { |
| 39 | +List<String>newTemp =newArrayList(temp); |
| 40 | +result.add(newTemp); |
| 41 | + } |
| 42 | +for (inti =start;i <s.length();i++) { |
| 43 | +if (dp[start][i]) { |
| 44 | +temp.add(s.substring(start,i +1)); |
| 45 | +backtracking(s,i +1,dp,temp,result); |
| 46 | +temp.remove(temp.size() -1); |
| 47 | + } |
| 48 | + } |
63 | 49 | } |
64 | | - } |
65 | 50 | } |
66 | | - } |
67 | 51 | } |