⚡Flashcard Drill➔
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

  1. Greedily pack words into a line while the length plus at least one space between each word fits within maxWidth.
  2. When a line is full, distribute the spaces: base = spaces // gaps for every gap, and the first spaces % gaps gaps get one extra space.
  3. A line with a single word is left-justified and padded with trailing spaces.
  4. 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, where len(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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems