Text Justification
Given an array of words and a width, justify the text by adding spaces between words so that each line has exactly width characters. If a line cannot be justified, add spaces to the left of the line. The last line should be left-justified.
Constraints:
- 1 <= words.length <= 300
- 1 <= width <= 100
- 1 <= words[i].length <= 20
Examples:
Input: ["This", "is", "an", "example", "of", "text", "justification."]
Output: ["This is an", "example of text", "justification. "]
Explanation: The first line has 13 characters (This + is + an), so we add 4 spaces to the right. The second line has 15 characters (example + of + text), so we add 2 spaces to the right. The last line has 15 characters (justification), so we add 7 spaces to the right.
Solutions
Greedy Algorithm
The solution uses a greedy algorithm to justify the text. It iterates over the words and adds them to the current line. If the current line exceeds the maximum width, it justifies the current line and adds it to the result. The last line is left-justified.
def fullJustify(words, maxWidth):
result, currentLine, currentWidth = [], [], 0
for word in words:
if currentWidth + len(word) + len(currentLine) > maxWidth:
spaces = maxWidth - currentWidth
gaps = len(currentLine) - 1
if gaps == 0:
result.append(currentLine[0] + " " * spaces)
else:
spaceEachGap = spaces // gaps
extraSpaces = spaces % gaps
line = ""
for i in range(len(currentLine)):
line += currentLine[i]
if i < len(currentLine) - 1:
line += " " * (spaceEachGap + (1 if i < extraSpaces else 0))
result.append(line)
currentLine, currentWidth = [word], len(word)
else:
currentLine.append(word)
currentWidth += len(word)
lastLine = " ".join(currentLine)
lastLine += " " * (maxWidth - len(lastLine))
result.append(lastLine)
return resultFollow-up:
How would you handle the case where the input words are not separated by spaces?
