68.文本左右对齐
68. 文本左右对齐
题意
给定一个单词数组 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","co
mputer.","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 "
]
分析
如果本题只是一般的左对齐，那么就非常简单，只需要依次添加字符串和一个空格，然后
等到剩余的格子数量不够填充了，再直接全部替换为空格即可，可惜本题是——左右两端
对齐。
这使得我们不得不去考虑每个单词之间空格的划分问题。
我们先来考虑除去单词后剩余的空格数量。
如果这一行一共能放下 n 个单词，那么就会有 n-1 个空隙，而我们所要做的，就是把剩余
的空格尽量均匀地分配到这 n-1 个空隙当中，如果不能均分，则要让靠左间隙的空格数量
大于等于靠右的空格数量。
除此之外，还有一些情况需要我们左对齐：
• 最后一行
• 该行只有一个单词
这两种情况下，我们需要左对齐——即”单词+空格+单词+……+单词+空格“的方式对齐即
可。
说起来简单，做起来难，我们在均分空隙的时候，仍然有很多的细节需要考虑。大家可以
结合代码去加深理解。
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> res = new ArrayList<>();
List<String> temp = new ArrayList<>();
for(int i = 0;i < words.length;){
temp.clear();
temp.add(words[i]);
int len = words[i].length();
i++;
while(i < words.length && len + 1 + words[i].length() <= maxWidth){
len += 1 + words[i].length();
temp.add(words[i]);
i++;
}
if(i == words.length){
StringBuilder add = new StringBuilder();
for (String s : temp) {
add.append(s).append(" ");
}
add.deleteCharAt(add.length() - 1);
for(int j = add.length();j < maxWidth;j++)
add.append(" ");
res.add(add.toString());
}
else
if(temp.size() == 1){
StringBuilder add = new StringBuilder(temp.get(0));
while(add.length() < maxWidth) add.append(" ");
res.add(add.toString());
}
else {
//len 是"单词+一个空格+单词+……+空格+单词"*单词数量
int wordLength = len - (temp.size() - 1);
//最大长度-wordLength 即为我们可以分配的空格总数
int spaceLength = maxWidth - wordLength;
//进行分配时候的单位空格长度（下取整）
int singleSpace = spaceLength / (temp.size() - 1);
StringBuilder space = new StringBuilder();
space.append(" ".repeat(Math.max(0, singleSpace)));
StringBuilder add = new StringBuilder();
int totSpaceLength = 0;
for(int j = 0;j < temp.size();j++){
add.append(temp.get(j));
if(j == temp.size() - 1)
break;
add.append(space);
totSpaceLength += singleSpace;
if((temp.size() - j - 2) * singleSpace + totSpaceLength <
spaceLength){
add.append(" ");
totSpaceLength++;
}
}
res.add(add.toString());
}
}
return res;
}
}
1672109376296-704b9522-b52c-4e46-bf8a-af31e3805cba.png
总结
本题是一道难度较高的字符串模拟，需要细心地观察和思考，一步步来，才能把这题的每
个部分”解剖“完成。
力扣链接：https://leetcode.cn/problems/text-justification/