image.png
0. 链接
1. 题目
Given an array of 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 do 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 " instead of "shall be",
because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified becase 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 "
]
2. 思路1：从左到右逐行填充
分析题意:
- 非最后一行,如果多于一个单词,则空格数按照尽量平均的方式分布于单词之间,且越靠近左边的空隙空格数越多
- 非最后一行，如果只能放得下一个单词，则靠左放置, 右边补充空格
- 最后一行，单词尽量靠左排列, 单词之间空隙只填充一个空格, 如果这样不能充满一行，则右边补充空格
3. 代码
# coding:utf8
from typing import List
import math
class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
results = list()
width = maxWidth
start_idx = 0
end_idx = 0
i = 0
while i < len(words):
# 从左到右尝试每一个单词
need_check = False
if width >= len(words[i]):
# 剩余宽度还可以容纳当前单词
width -= len(words[i]) + 1 # 但实际扣除时需要多扣除单词后的1个空格, 所以width最小可以是-1
end_idx = i
i += 1
if i == len(words):
# 提前到达最后一个单词, 需要提前做终止处理
need_check = True
else:
need_check = True
if need_check:
# 填充一行
num = end_idx - start_idx + 1
if end_idx == len(words) - 1:
# 最后一行, 空格规则不同, 单独处理
empty_spaces = width
result = list()
for j in range(start_idx, end_idx):
result.append(words[j] + ' ')
if empty_spaces >= 0:
# 最后一个单词后也可以跟至少一个空格
result.append(words[end_idx] + ' ')
if empty_spaces > 0:
# 还有多余的空格, 追加到末尾
result.append(' ' * empty_spaces)
else:
# 最后一个单词后面没法加空格了
result.append(words[end_idx])
# 将最后一行添加到结果列表
results.append(''.join(result))
elif num > 1:
# 非最后一行, 且单词数不止1个
empty_spaces = width + num # 总空格数, 包含了每个单词后的那个空格
blank = math.ceil(empty_spaces / (num - 1)) # 平均起来每两个单词间可以插入的空格
full_count = num - 1 - (blank * (num - 1) - empty_spaces) # 可以按平均空格插入的空隙数
full_idx = start_idx + full_count - 1 # 最后一个可以插入平均空格的空隙序号
# 依次处理这一行的每个单词
result = list()
for j in range(start_idx, end_idx + 1):
if j <= full_idx:
# 前若干个空隙, 可以插入足量空格数
result.append(words[j] + ' ' * blank)
elif j < end_idx:
# 后面若干个空隙, 可以插入少一个空格数
result.append(words[j] + ' ' * (blank - 1))
else:
# 最后一个单词尾部不加空格
result.append(words[j])
results.append(''.join(result))
else:
# 非最后一行, 且单词数只有一个
results.append(words[start_idx] + ' ' * (maxWidth - len(words[start_idx])))
# 下一行的首个单词的序号, 重置可用宽度
width = maxWidth
start_idx = i
return results
def print_list(list):
for each in list:
print(each)
print('=' * 50)
solution = Solution()
print_list(solution.fullJustify(['This', 'is', 'an', 'example', 'of', 'text', 'justification'], 16))
print_list(solution.fullJustify(['What', 'must', 'be', 'acknowledgment', 'shall', 'be'], 16))
print_list(solution.fullJustify(['Science', 'is', 'what', 'we', 'understand', 'well', 'enough', 'to', 'explain',
'to', 'a', 'computer.', 'Art', 'is', 'everything', 'else', 'we', 'do'], 20))
print(solution.fullJustify(["ask","not","what","your","country","can","do","for","you","ask","what",
"you","can","do","for","your","country"], 16))
输出结果
This is an
example of text
justification
==================================================
What must be
acknowledgment
shall be
==================================================
Science is what we
understand well
enough to explain to
a computer. Art is
everything else we
do
==================================================
ask not what
your country can
do for you ask
what you can do
for your country
==================================================
4. 结果
image.png
