|
5 | 5 | importjava.util.List; |
6 | 6 |
|
7 | 7 | publicclassPartition { |
8 | | -publicList<List<String>>partition(Strings) { |
| 8 | +publicList<List<String>>partition1(Strings) { |
9 | 9 | List<List<String>>ret =newArrayList<List<String>>(); |
10 | 10 | List<String>path =newArrayList<String>(); |
11 | 11 |
|
@@ -64,13 +64,63 @@ public void dfs(String s, List<String> path, List<List<String>> ret, int index, |
64 | 64 | path.remove(path.size() -1); |
65 | 65 | } |
66 | 66 | } |
| 67 | + |
| 68 | +publicList<List<String>>partition(Strings) { |
| 69 | +List<List<String>>ret =newArrayList<List<String>>(); |
| 70 | +List<String>path =newArrayList<String>(); |
| 71 | + |
| 72 | +if (s ==null) { |
| 73 | +returnret; |
| 74 | + } |
| 75 | + |
| 76 | +boolean[][]isPalindrom =buildPalindromDP(s); |
| 77 | + |
| 78 | +dfs2(s,path,ret,0,isPalindrom); |
| 79 | + |
| 80 | +returnret; |
| 81 | + } |
67 | 82 |
|
68 | 83 | /* |
69 | 84 | * Solution 2: Use DP to reduce the duplicate count. |
70 | 85 | * */ |
71 | | -boolean[][]isPalindromDP(Strings) { |
| 86 | +boolean[][]buildPalindromDP(Strings) { |
72 | 87 | intlen =s.length(); |
73 | | -boolean[][]ret =newboolean[len][len]; |
| 88 | +boolean[][]D =newboolean[len][len]; |
| 89 | + |
| 90 | +for (intj =0;j <len;j++) { |
| 91 | +for (inti =0;i <=j;i++) { |
| 92 | +if (j ==0) { |
| 93 | +D[i][j] =true; |
| 94 | +continue; |
| 95 | + } |
| 96 | + |
| 97 | +// 注意，这里要加上j - i <= 2否则会越界 |
| 98 | +D[i][j] =s.charAt(i) ==s.charAt(j) |
| 99 | + && (j -i <=2 ||D[i +1][j -1]); |
| 100 | + } |
| 101 | + } |
| 102 | + |
| 103 | +returnD; |
| 104 | + } |
| 105 | + |
| 106 | +/* |
| 107 | + we use a map to store the solutions to reduce the times of computing. |
| 108 | + */ |
| 109 | +publicvoiddfs2(Strings,List<String>path,List<List<String>>ret,intindex,boolean[][]isPalindromDP) { |
| 110 | +if (index ==s.length()) { |
| 111 | +ret.add(newArrayList<String>(path)); |
| 112 | +return; |
| 113 | + } |
| 114 | + |
| 115 | +for (inti =index;i <s.length();i++) { |
| 116 | +Stringsub =s.substring(index,i +1); |
| 117 | +if (!isPalindromDP[index][i]) { |
| 118 | +continue; |
| 119 | + } |
| 120 | + |
| 121 | +path.add(sub); |
| 122 | +dfs2(s,path,ret,i +1,isPalindromDP); |
| 123 | +path.remove(path.size() -1); |
| 124 | + } |
74 | 125 | } |
75 | | - |
76 | 126 | } |