Date and Time: Jul 10, 2024, 14:48 (EST)
Link: https://leetcode.com/problems/text-justification/
Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left-justified, and no extra space is inserted between words.
Note:
-
A word is defined as a character sequence consisting of non-space characters only.
-
Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.
-
The input array words contains at least one word.
Example 1:
Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[
"This is an",
"example of text",
"justification. "
]
Example 2:
Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output:
[
"What must be",
"acknowledgment ",
"shall be "
]
Explanation: Note that the last line is
"shall be \space "instead of"shall \space be", because the last line must be left-justified instead of fully-justified. Note that the second line is also left-justified because it contains only one word.
Example 3:
Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20
Output:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]
-
1 <= words.length <= 300 -
1 <= words[i].length <= 20 -
words[i]consists of only English letters and symbols. -
1 <= maxWidth <= 100 -
words[i].length <= maxWidth
We repeatedly append each word to tmp[] and each word's length to length, if the next word word[i]'s length > maxWidth, we should stop adding this word to current row.
Then, we check how many spaces we need to insert among len(tmp) - 1 elements (len(tmp) is how many elements we added so far) by maxWidth - length, we use (maxWidth - length) // max(1, len(tmp)-1) to know how many spaces to add among each elements in tmp except the last element, and we use max(1, len(tmp)-1) to avoid the case that tmp has only one element, so we want the element to be at least 1. Sometimes it is possible the spaces can't be distributed evenly, so we have remainder = (maxWidth - length) % max(1, len(tmp)-1) as we append to each word and decrement remainder (guaranteed that more spaces on the left).
Next, we reset tmp, length = [], 0 and use "".join(tmp) to make all elements in tmp to be string and append it to res.
Finally, after the for loop is done, we will have one extra line left (as you can see from examples usually the last line can't satisfy if length + len(tmp) + len(words[i]) > maxWidth because we just reset tmp, length). So, we handle it by adding space " ".join(tmp) to put them all together in one line with space in case we have more than one word in the lastLine. Since the last line of text should be left-justified, and no extra space is inserted between words, we should only add extra spaces " " * (maxWidth - len(lastLine)) in the end of lastLine.
For each line, we only append spaces among words. So we should check if there is a case for a long word in a line.
class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
# Each line will have max maxWidth, keep wordList[], strCount(int) for each line, if we try adding a new word > maxWidth, stop. To count each line: strCount + len(wordList) < maxWidth
# Spaces: maxWidth - strCount - len(wordList) // len(wordList), extraSpace = maxWidth - strCount - len(wordList) % len(wordList)
# Last line: spaces: len(wordList), append all the extraSpace to the end: maxWidth - strCount - len(wordList)
# TC: O(n), n=all chars, SC: O(n)
res = [] # Final answer
wordList = []
strCount = 0
for word in words:
# Process each word into wordList and strCount
# Try if we can still add a new word
if strCount + len(wordList) + len(word) <= maxWidth:
strCount += len(word)
wordList.append(word)
else:
# Process spaces when line is full, exclude the last word
avgSpaces = (maxWidth - strCount) // max(1, len(wordList)-1)
extraSpaces = maxWidth - strCount - (avgSpaces * max(1, len(wordList)-1))
# Process and append new line to res[]
line = ""
# Account for a single word in a line
if len(wordList) == 1:
line += wordList[0] + " " * (avgSpaces + extraSpaces)
# If more than one word in a line, we only append spaces among words
else:
for i, w in enumerate(wordList):
line += w
# Except the last word
if i < len(wordList) - 1:
line += " " * avgSpaces
if extraSpaces:
line += " "
extraSpaces -= 1
res.append(line)
# Reset
wordList = [word]
strCount = len(word)
# Handle last line, after last word, process whatever we have
line = " ".join(wordList) # Join each word with a space
line += " " * (maxWidth - len(line))
res.append(line)
return resTime Complexity: n = len(words).
Space Complexity:
Jun 1, 2026
class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
# Q: 1. Each line should satisfy maxWidth, if not, i. If can be evenly split, put more space; if not, pad more space to the left.
# 2. Last line should be left-justified
# S: 1. Process word by word, after each word, add one space, check if adding the new word < maxWidth. If not, maxWidth-total_width // curr_num_word, append maxWidth-total_width % curr_num_word to the space after the first word.
# 2. Last line: add all extra spaces to the end.
# TC: O(n*k), n=len(words), k=max(word_len), SC: O(maxWidth)
res = []
cnt = 0
wordLst = []
for word in words:
# Check if we can add word to wordLst by counting existing words (cnt), spaces needed for len(wordLst)
if cnt + len(word) + len(wordLst) <= maxWidth:
cnt += len(word)
wordLst.append(word)
# If cannot add new word, process the current line and add it into new line
else:
# TODO: handle even len(wordLst) and odd len(wordLst) cases
# We always need len(wordLst) - 1 for space slot
total_space = maxWidth - cnt
avg_space = total_space // max(1, (len(wordLst) - 1))
extraspace = total_space - (avg_space * max(1, (len(wordLst)-1)))
line = ""
# Handle case when we have single word
if len(wordLst) == 1:
line = wordLst[0] + " " * total_space
else:
for i, w in enumerate(wordLst):
line += w
# Except the last word
if i < len(wordLst) - 1:
line += " " * avg_space
# Process extraSpace
if extraspace:
line += " "
extraspace -= 1
# Add line to res[]
res.append(line)
# Reset line, cnt, wordLst, and add word into wordLst
line = ""
cnt = len(word)
wordLst = [word]
# e.g. 7 space for [w1 w2 w3], avg=7//2 = 3, extra = 7%2=1
# TODO: Handle last line, because after we add the last word, we will not be able to process in the for loop
line = " ".join(wordLst) # join every word with a space
line += (" " * (maxWidth - len(line)))
res.append(line)
return res
