You are given a list of words and a line width maxWidth. Put the words into lines so that every line has exactly maxWidth characters, and the text is justified on both sides (left and right), like in a newspaper column.
Follow these rules:
- Fill each line greedily: put as many words as fit on a line, with at least one space between two words.
- Spread the extra spaces between the words on the line as evenly as possible.
- If the extra spaces cannot be shared equally, the gaps on the left get more spaces than the gaps on the right.
- The last line is only left-aligned. Its words are separated by single spaces, and the rest of the line is filled with spaces at the end.
- A line that has only one word is also left-aligned and filled with spaces at the end.
A word has no spaces in it. Every word is at least one character long and not longer than maxWidth. The list has at least one word.
Return the list of lines.
Examples
Example 1:
Input: words = ["Study","hard","and","code","every","day"], maxWidth = 15
Output: ["Study hard and","code every day "]
Explanation: The first line has 3 words and 3 spare spaces, so the left gap gets 2 and the right gap gets 1. The last line is left-aligned and padded at the end.
Example 2:
Input: words = ["Hello"], maxWidth = 8
Output: ["Hello "]
Explanation: One word on the last line is left-aligned and padded with spaces.
Example 3:
Input: words = ["We","love","clean","code","very","much"], maxWidth = 12
Output: ["We love","clean code","very much "]
Explanation: A line with two words has one gap, which takes all the spare spaces. The last line "very much" is left-aligned and padded at the end.