How do I approach the Text Justification problem?

Start by packing words into lines using a greedy approach, ensuring the total line width does not exceed maxWidth. Then, distribute spaces evenly between the words, with extra spaces placed on the left. Finally, make sure the last line is left-justified.

What happens if the spaces can't be evenly distributed?

If the spaces cannot be evenly distributed, the extra spaces are added from left to right, meaning the leftmost spaces will get more space than the rightmost.

Why is the last line always left-justified?

The last line is left-justified to ensure that no extra space is added between words, and the remaining space is filled at the end of the line.

How do I handle edge cases like a single word on a line?

If there's only one word on the line, the line will be left-justified, and the remaining spaces will be added at the end of the line.

What is the time complexity of solving Text Justification?

The time complexity is typically O(n), where n is the number of words. This involves iterating over the words and distributing spaces in each line.

#68

Hard

auto_awesome数组·string

LeetCode 题解工作台

文本左右对齐

给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。你应该使用 “ 贪心算法 ” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字…

数组字符串模拟

题目描述

给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

注意:

单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。

示例 1:

输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
输出:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

示例 2:

输入:words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
输出:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
     因为最后一行应为左对齐，而不是左右两端对齐。       
     第二行同样为左对齐，这是因为这行只包含一个单词。

示例 3:

输入:words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]，maxWidth = 20
输出:
[
  "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] 由小写英文字母和符号组成
1 <= maxWidth <= 100
words[i].length <= maxWidth

lightbulb

解题思路

方法一：模拟

根据题意模拟即可，注意，如果是最后一行，或者这一行只有一个单词，那么要左对齐，否则要均匀分配空格。

时间复杂度 $O(L)$ ，空间复杂度 $O(L)$ 。其中 $L$ 为所有单词的长度之和。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        ans = []
        i, n = 0, len(words)
        while i < n:
            t = []
            cnt = len(words[i])
            t.append(words[i])
            i += 1
            while i < n and cnt + 1 + len(words[i]) <= maxWidth:
                cnt += 1 + len(words[i])
                t.append(words[i])
                i += 1
            if i == n or len(t) == 1:
                left = ' '.join(t)
                right = ' ' * (maxWidth - len(left))
                ans.append(left + right)
                continue
            space_width = maxWidth - (cnt - len(t) + 1)
            w, m = divmod(space_width, len(t) - 1)
            row = []
            for j, s in enumerate(t[:-1]):
                row.append(s)
                row.append(' ' * (w + (1 if j < m else 0)))
            row.append(t[-1])
            ans.append(''.join(row))
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Able to explain space distribution in detail.
question_mark
Can implement a greedy approach effectively.
question_mark
Demonstrates understanding of left justification and its edge cases.

warning

常见陷阱

外企场景

error
Incorrectly distributing spaces when the number of spaces doesn't divide evenly.
error
Forgetting that the last line should be left-justified.
error
Overcomplicating the space distribution by adding extra checks.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling very large maxWidth values.
arrow_right_alt
Handling words with different lengths efficiently.
arrow_right_alt
Implementing an alternative approach that minimizes space usage while keeping time complexity optimal.

help

常见问题

外企场景

继续练习

#67 二进制求和 #59 螺旋矩阵 II #79 单词搜索