1+ package Algorithms .string ;
2+
3+ import java .util .ArrayList ;
4+ import java .util .List ;
5+
6+ public class FullJustify {
7+ public static void main (String []strs ) {
8+ String []words = {"Listen" ,"to" ,"many," ,"speak" ,"to" ,"a" ,"few." };
9+ int L =6 ;
10+ fullJustify (words ,L );
11+ }
12+
13+ // SOLUTION 1: recursion.
14+ public List <String >fullJustify1 (String []words ,int L ) {
15+ List <String >ret =new ArrayList <String >();
16+
17+ if (words ==null ) {
18+ return ret ;
19+ }
20+
21+ rec (words ,L ,0 ,ret );
22+ return ret ;
23+ }
24+
25+ public static void rec (String []words ,int L ,int index ,List <String >list ) {
26+ int len =words .length ;
27+ if (index >=len ) {
28+ return ;
29+ }
30+
31+ int LenTmp =L ;
32+
33+ int end =index ;
34+ for (int i =index ;i <len &&words [i ].length () <=L ;i ++) {
35+ L -=words [i ].length ();
36+
37+ // the space follow the word.
38+ L --;
39+ end =i ;
40+ }
41+
42+ // 最后一个空格收回
43+ L ++;
44+
45+ // Count how many words do we have.
46+ int num =end -index +1 ;
47+
48+ int extraSpace =0 ;
49+ int firstExtra =0 ;
50+
51+ // 单词数大于1，才需要分配，否则所有的空格加到最后即可
52+ if (num >1 ) {
53+ extraSpace =L / (num -1 );
54+ // 首单词后多跟的空格
55+ firstExtra =L % (num -1 );
56+ }
57+
58+ StringBuilder sb =new StringBuilder ();
59+ for (int i =index ;i <=end ;i ++) {
60+ sb .append (words [i ]);
61+
62+ // The space following every word.
63+ if (i !=end ) {
64+ sb .append (' ' );
65+ }
66+
67+ // 不是最后一行
68+ if (end !=len -1 ) {
69+ // The first words.
70+ if (firstExtra >0 ) {
71+ sb .append (' ' );
72+ firstExtra --;
73+ }
74+
75+ // 最后一个单词后面不需要再加空格
76+ if (i ==end ) {
77+ break ;
78+ }
79+
80+ // 每个单词后的额外空格
81+ int cnt =extraSpace ;
82+ while (cnt >0 ) {
83+ sb .append (' ' );
84+ cnt --;
85+ }
86+ }
87+ }
88+
89+ // 最后一行的尾部的空格
90+ int tailLen =LenTmp -sb .length ();
91+ while (tailLen >0 ) {
92+ sb .append (' ' );
93+ tailLen --;
94+ }
95+
96+ list .add (sb .toString ());
97+ rec (words ,LenTmp ,end +1 ,list );
98+ }
99+
100+ // SOLUTION 2: iteration.
101+ public List <String >fullJustify (String []words ,int L ) {
102+ List <String >ret =new ArrayList <String >();
103+
104+ if (words ==null ) {
105+ return ret ;
106+ }
107+
108+ rec (words ,L ,0 ,ret );
109+ return ret ;
110+ }
111+ }