Justify Text

Newspaper columns stretch the spaces between words so that every line ends exactly at the right margin. Write justify(words, width) that lays out words in lines of width characters and returns the lines as a list of strings.

• Fill the lines greedily: put as many words on a line as fit with at least one space between neighbours, then start the next line.
• Stretch every line except the last to exactly width characters by sharing the spaces between its gaps as evenly as possible. When they do not share out evenly, gaps further left get one more space than gaps further right.
• A line with only one word that is not the last line is padded with spaces on the right up to width.
• The last line is not stretched: its words are separated by single spaces, and nothing comes after its last word.

Examples

justify(["Python", "makes", "text", "layout", "a", "breeze"], 14)
# returns ['Python   makes', 'text  layout a', 'breeze']
justify(["a", "b", "c", "d", "e"], 8)  # returns ['a  b c d', 'e']
justify(["Hi"], 10)                    # returns ['Hi']

In the first line, "Python" and "makes" use 11 characters, so the single gap gets all 3 spaces that are left. In the second line, 3 spaces are shared by 2 gaps: the left gap gets 2 and the right gap 1.

Constraints

• words has 0 to 1,000 items, and no words means no lines.
• Each word has 1 to width characters and contains no spaces.
• 1 <= width <= 100