Justify Lines to Width
words is a list of words and width is a line width; no word is longer than width. Lay the words out on lines in order, greedily: a line keeps taking the next word as long as the line still fits, where a line with m words fits when the lengths of its words plus m - 1 single spaces total at most width.
Then pad every line to exactly width characters:
- On every line except the last, spread the spare spaces over the gaps between its words as evenly as possible; when they cannot be spread evenly, the leftmost gaps get one extra space each, from left to right, until the extras run out. A line with a single word has no gap, so all its spaces go after the word.
- The last line is left-justified: single spaces between its words and all the spare spaces at the end.
Return the list of lines. When all the words fit on one line, that line is the last line.
Example 1
this is an has 8 letters and needs 8 spaces over 2 gaps, 4 each; example of text has 13 letters and 3 spaces over 2 gaps, so the left gap gets 2; the last line is padded on the right.
Example 2
what must be fills 16 with 3 extra spaces over 2 gaps, so the left gap gets one more; acknowledgment is alone on its line and the spaces go after it; shall be is the last line.
Constraints
1 <= len(words) <= 301 <= len(words[i]) <= width <= 30- words have lowercase letters and the punctuation
. , ! ?only
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.