Text Justification
Hard · Strings · Array · String · Simulation
Problem
Lay out the list words as fully justified text, every line exactly maxWidth characters wide.
- Packing is greedy: put as many words on a line as fit, with at least one space between neighboring words.
- Spaces are spread evenly between the words of a line. When they do not divide evenly, the gaps on the left get one more space than the gaps on the right.
- A line holding one word is left-justified: the word, then spaces up to maxWidth.
- The last line is left-justified as well: single spaces between its words, then spaces up to maxWidth.
Each word is a run of non-space characters, and no word is longer than maxWidth. Return the lines.
Examples
Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16 Output: ["This is an", "example of text", "justification. "]
Line 1 has 8 letters and 8 spaces in two gaps: 4 and 4. Line 2 has 13 letters and 3 spaces in two gaps: 2 on the left, 1 on the right.
Input: words = ["What", "must", "be", "acknowledgment", "shall", "be"], maxWidth = 16 Output: ["What must be", "acknowledgment ", "shall be "]
acknowledgment is alone on its line, so it is left-justified; the last line keeps single spaces.
Input: words = ["a", "b", "c", "dddddddd"], maxWidth = 8 Output: ["a b c", "dddddddd"]
Five spaces over two gaps: 3 on the left, 2 on the right.
Constraints
- 1 <= words.length <= 300
- 1 <= words[i].length <= 20
- words[i] holds English letters and symbols, never a space
- 1 <= maxWidth <= 100
- words[i].length <= maxWidth
Approaches
- Greedy lines, spaces by division — time O(L), space O(L)
Follow-up
Greedy packing can leave a very short line in the middle. With a cost per line such as the square of its trailing space, dynamic programming finds the line breaks with the least total cost (the idea behind TeX's line breaking). And how would you center each line instead?
Related problems
Start free on Cariara · Coding problems · System design studio
