1+ /*
2+ Author: Andy, nkuwjg@gmail.com
3+ Date: Jan 29, 2015
4+ Problem: Text Justification
5+ Difficulty: Hard
6+ Source: https://oj.leetcode.com/problems/text-justification/
7+ Notes:
8+ Given an array of words and a length L, format the text such that each line has exactly L
9+ characters and is fully (left and right) justified.
10+ You should pack your words in a greedy approach; that is, pack as many words as you can in each line.
11+ Pad extra spaces ' ' when necessary so that each line has exactly L characters.
12+ Extra spaces between words should be distributed as evenly as possible. If the number of spaces
13+ on a line do not divide evenly between words, the empty slots on the left will be assigned more
14+ spaces than the slots on the right.
15+ For the last line of text, it should be left justified and no extra space is inserted between words.
16+
17+ For example,
18+ words: ["This", "is", "an", "example", "of", "text", "justification."]
19+ L: 16.
20+ Return the formatted lines as:
21+ [
22+ "This is an",
23+ "example of text",
24+ "justification. "
25+ ]
26+ Note: Each word is guaranteed not to exceed L in length.
27+ Corner Cases:
28+ A line other than the last line might contain only one word. What should you do in this case?
29+ In this case, that line should be left-justified.
30+
31+ Solution: ...
32+ */
33+
34+ public class Solution {
35+ public List <String >fullJustify (String []words ,int L ) {
36+ List <String >res =new ArrayList <String >();
37+ int i =0 ,N =words .length ;
38+ while (i <N ) {
39+ int length =words [i ].length ();
40+ int j =i +1 ;
41+ while (j <N &&length +words [j ].length () + (j -i ) <=L ) {
42+ length +=words [j ++].length ();
43+ }
44+ StringBuilder s =new StringBuilder (words [i ]);
45+ boolean isLastLine = (j ==N );
46+ boolean oneWord = (j ==i +1 );
47+ int average = (isLastLine ||oneWord ) ?1 : (L -length )/(j -i -1 );
48+ int extra = (isLastLine ||oneWord ) ?0 : (L -length )%(j -i -1 );
49+ for (int k =i +1 ;k <j ; ++k ) {
50+ char []tmp =new char [extra >0 ?average +1 :average ];
51+ Arrays .fill (tmp ,' ' );
52+ s .append (tmp );
53+ s .append (words [k ]);
54+ extra --;
55+ }
56+ char []tmp =new char [L -s .length ()];
57+ Arrays .fill (tmp ,' ' );
58+ s .append (tmp );
59+ res .add (s .toString ());
60+ i =j ;
61+ }
62+ return res ;
63+ }
64+ }
