11public class Solution {
22
3- final int STACK_SIZE = 10 ;
4-
5- String [] stack ;
6- ArrayList < String > found ;
7-
8- void pushWord (int p , String word ){
9- while ( p >= stack . length ){
10- stack = Arrays . copyOf ( stack , stack . length + STACK_SIZE );
3+ String join ( List < String > list ){
4+ if ( list . isEmpty ()) return "" ;
5+
6+ StringBuilder s = new StringBuilder ( list . get ( 0 )) ;
7+
8+ for (int i = 1 ; i < list . size (); i ++ ){
9+ s . append ( ' ' );
10+ s . append ( list . get ( i ) );
1111 }
12-
13- stack [ p ] = word ;
12+
13+ return s . toString () ;
1414 }
1515
16- void wordBreak (String s ,Set <String >dict ,final int p ){
17- if ("" .equals (s ) ||s ==null ){
18-
19- if (p >0 ){
20- String join =stack [0 ];
21- for (int i =1 ;i <p ;i ++){
22- join +=" " +stack [i ];
23- }
24-
25- found .add (join );
26- }
16+ ArrayList <Integer >[]P ;
17+ char []S ;
18+ ArrayList <String >rt ;
19+
20+ void joinAll (int offset ,LinkedList <String >parents ){
21+
22+ if (P [offset ].isEmpty ()){
2723
24+ rt .add (join (parents ));
2825return ;
2926 }
3027
31- for (String d :dict ){
32- if (s .startsWith (d )){
33-
34- int l =d .length ();
35- pushWord (p ,d );
36-
37- wordBreak (s .substring (l ),dict ,p +1 );
38- }
28+ for (Integer p :P [offset ]){
29+
30+ parents .push (new String (S ,p ,offset -p ));
31+
32+ joinAll (p ,parents );
33+
34+ parents .pop ();
3935 }
4036
4137 }
42-
43- boolean _wordBreak (String s ,Set <String >dict ) {
44-
45- char []S =s .toCharArray ();
46-
47- boolean []P =new boolean [S .length +1 ];
48- P [0 ] =true ;
49-
38+
39+ public List <String >wordBreak (String s ,Set <String >dict ) {
40+ S =s .toCharArray ();
41+
42+ P =new ArrayList [S .length +1 ];
43+ P [0 ] =new ArrayList <Integer >();
44+
5045for (int i =0 ;i <S .length ;i ++){
51-
5246for (int j =0 ;j <=i ;j ++){
53- if (P [j ] &&dict .contains (new String (S ,j ,i -j +1 ))){
54- P [i +1 ] =true ;
55- continue ;
47+ String w =new String (S ,j ,i -j +1 );
48+ if (P [j ] !=null &&dict .contains (w )){
49+
50+ if (P [i +1 ] ==null ){
51+ P [i +1 ] =new ArrayList <Integer >();
52+ }
53+
54+ P [i +1 ].add (j );
5655 }
5756 }
5857 }
58+
59+ rt =new ArrayList <String >();
5960
60- return P [S .length ];
61-
62-
63- }
64-
65- public ArrayList <String >wordBreak (String s ,Set <String >dict ) {
66- // Note: The Solution object is instantiated only once and is reused by each test case.
67-
68- found =new ArrayList <String >();
69-
70- if (_wordBreak (s ,dict )){
71- if (dict .size () <=0 )return found ;
72- stack =new String [STACK_SIZE ];
73-
74- wordBreak (s ,dict ,0 );
61+ if (P [S .length ] !=null ){
62+ joinAll (S .length ,new LinkedList <String >());
7563 }
7664
77- return found ;
65+ return rt ;
7866 }
79- }
67+ }