NeetCode #168LC-68HardArrays & Hashing
← Back to All Problems#168 · #68 · Text Justification(文本左右对齐)
📌 Problem Statement & Constraints
Given an array of words and a width
maxWidth, format the text so that each line has exactly maxWidth characters and is fully justified. Extra spaces are distributed as evenly as possible, with the left slots getting more. The last line is left-justified with no extra spacing. Constraints: 1 <= words.length <= 300, 1 <= maxWidth <= 100.💡 Core Algorithmic Approaches
- Greedily pack words into a line while the length plus at least one space between each word fits within
maxWidth. - When a line is full, distribute the spaces:
base = spaces // gapsfor every gap, and the firstspaces % gapsgaps get one extra space. - A line with a single word is left-justified and padded with trailing spaces.
- The final line is always left-justified: words joined by single spaces, then padded at the end.
💻 Benchmark Python3 Implementation
class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
res = []
cur = [] # words on the current line
cur_len = 0 # sum of their lengths
for w in words:
# adding w needs len(w) plus one separating space per existing word
if cur_len + len(w) + len(cur) > maxWidth:
if len(cur) == 1:
res.append(cur[0] + " " * (maxWidth - len(cur[0])))
else:
spaces = maxWidth - cur_len
gaps = len(cur) - 1
base, extra = divmod(spaces, gaps)
line = []
for i, x in enumerate(cur[:-1]):
# the first `extra` gaps receive one additional space
line.append(x + " " * (base + (1 if i < extra else 0)))
line.append(cur[-1])
res.append("".join(line))
cur = []
cur_len = 0
cur.append(w)
cur_len += len(w)
# last line: left-justified, padded on the right
last = " ".join(cur)
res.append(last + " " * (maxWidth - len(last)))
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(total characters): each word is placed once and each line's padding is generated once.
💾 Space Complexity
O(maxWidth) per line for the constructed string.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the separating space when testing the fit: the condition is
cur_len + len(w) + len(cur) > maxWidth, wherelen(cur)accounts for one space per existing word. - Distributing extra spaces to the rightmost gaps: the problem requires the left gaps to receive the extra space, hence
i < extra. - Justifying the last line: it must be left-justified with trailing padding, not fully justified.
- Dividing by zero gaps: a single-word line must be handled separately, since
gaps == 0. - Not padding the last line: the total width must still be exactly
maxWidth.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.