1+ package Algorithms .dfs ;
2+
3+ import java .util .ArrayList ;
4+ import java .util .HashMap ;
5+ import java .util .List ;
6+
7+ public class Partition_2014_1229 {
8+ // Solution 1: The DFS version.
9+ public List <List <String >>partition1 (String s ) {
10+ List <List <String >>ret =new ArrayList <List <String >>();
11+ if (s ==null ) {
12+ return ret ;
13+ }
14+
15+ dfs (s ,0 ,new ArrayList <String >(),ret );
16+ return ret ;
17+ }
18+
19+ public static void dfs (String s ,int index ,List <String >path ,List <List <String >>ret ) {
20+ int len =s .length ();
21+ if (index ==len ) {
22+ ret .add (new ArrayList <String >(path ));
23+ return ;
24+ }
25+
26+ for (int i =index ;i <len ;i ++) {
27+ String sub =s .substring (index ,i +1 );
28+ if (!isPalindrome (sub )) {
29+ continue ;
30+ }
31+
32+ path .add (sub );
33+ dfs (s ,i +1 ,path ,ret );
34+ path .remove (path .size () -1 );
35+ }
36+ }
37+
38+ public static boolean isPalindrome (String s ) {
39+ int len =s .length ();
40+ int left =0 ;
41+ int right =len -1 ;
42+
43+ while (left <right ) {
44+ if (s .charAt (left ) !=s .charAt (right )) {
45+ return false ;
46+ }
47+ left ++;
48+ right --;
49+ }
50+
51+ return true ;
52+ }
53+
54+ // Solution 2: The DFS version with memory.
55+ public List <List <String >>partition2 (String s ) {
56+ List <List <String >>ret =new ArrayList <List <String >>();
57+ if (s ==null ) {
58+ return ret ;
59+ }
60+
61+ // bug: new map error.
62+ dfs2 (s ,0 ,new ArrayList <String >(),ret ,new HashMap <String ,Boolean >());
63+ return ret ;
64+ }
65+
66+ public static void dfs2 (String s ,int index ,List <String >path ,List <List <String >>ret ,HashMap <String ,Boolean >map ) {
67+ int len =s .length ();
68+ if (index ==len ) {
69+ ret .add (new ArrayList <String >(path ));
70+ return ;
71+ }
72+
73+ for (int i =index ;i <len ;i ++) {
74+ String sub =s .substring (index ,i +1 );
75+ if (!isPalindromeHash (sub ,map )) {
76+ continue ;
77+ }
78+
79+ path .add (sub );
80+ dfs2 (s ,i +1 ,path ,ret ,map );
81+ path .remove (path .size () -1 );
82+ }
83+ }
84+
85+ // BUG 3: use boolean instead of Boolean.
86+ public static boolean isPalindromeHash (String s ,HashMap <String ,Boolean >map ) {
87+ int len =s .length ();
88+ int left =0 ;
89+ int right =len -1 ;
90+
91+ if (map .get (s ) !=null ) {
92+ return map .get (s );
93+ }
94+
95+ map .put (s ,true );
96+ while (left <right ) {
97+ if (s .charAt (left ) !=s .charAt (right )) {
98+ map .put (s ,false );
99+ return false ;
100+ }
101+ left ++;
102+ right --;
103+ }
104+
105+ return true ;
106+ }
107+
108+ // Solution 3: Use DP to determine the palindrome first.
109+ public List <List <String >>partition (String s ) {
110+ List <List <String >>ret =new ArrayList <List <String >>();
111+ if (s ==null ) {
112+ return ret ;
113+ }
114+
115+ int len =s .length ();
116+
117+ // D[i][j]: if this a palindrom for s.substring(i, j + 1).
118+ boolean [][]D =new boolean [len ][len ];
119+
120+ for (int j =0 ;j <len ;j ++) {
121+ for (int i =0 ;i <=j ;i ++) {
122+ D [i ][j ] =s .charAt (i ) ==s .charAt (j ) && (j -i <=2 ||D [i +1 ][j -1 ]);
123+ }
124+ }
125+
126+ // bug: new map error.
127+ dfs3 (s ,0 ,new ArrayList <String >(),ret ,D );
128+ return ret ;
129+ }
130+
131+ public static void dfs3 (String s ,int index ,List <String >path ,List <List <String >>ret ,boolean [][]D ) {
132+ int len =s .length ();
133+ if (index ==len ) {
134+ ret .add (new ArrayList <String >(path ));
135+ return ;
136+ }
137+
138+ for (int i =index ;i <len ;i ++) {
139+ String sub =s .substring (index ,i +1 );
140+ if (!D [index ][i ]) {
141+ continue ;
142+ }
143+
144+ path .add (sub );
145+ dfs3 (s ,i +1 ,path ,ret ,D );
146+ path .remove (path .size () -1 );
147+ }
148+ }
149+ }
