Text Justification

Description

We are given an array of strings and a maximum width. We have to format the input words in the same order and into several rows with n columns. The words must be formatted such that each line has exactly n characters, one in each column, except possibly the last line. We must squeeze as many words as possible into each line, with at least one space between each pair of consecutive words. The first word on each line must start at the left-most column.

The last word on each line must end at the right-most column, unless only one word can fit on a line. More than one space between words may need to be inserted to ensure that the first word in a line starts at the first column and the last word ends at the last column. In such cases, we will insert an approximately equal number of spaces between each pair of words. If the spaces can’t be evenly spread between the words on a line, then the first two words will get more spaces than all the other word pairs, which will be spaced equally.

The last line must start on the left-most column, but may end before the last column. Only one space between each pair of words must be used on the last line. We will put as many words as we can in each line. We will add extra spaces, when necessary, so that each line has exactly the given width of characters. We will distribute extra spaces between words as evenly as possible. Otherwise, the empty slots on the left will have more spaces than the slots on the right.

Note: A word consists of non-space characters only. Each word’s length must be greater than 0 and should not exceed the given width. The input array will contain at least one word.

Constraints

• 1 <= words.length <= 300
• 1 <= words[i].length <= 20
• 1 <= width <= 100
• words[i].length <= width
• words[i] consists of only English letters and symbols.

Let’s see the example in the following illustration: