问题描述
给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。
注意:
- 单词是指由非空格字符组成的字符序列。
- 每个单词的长度大于 0，小于等于 maxWidth。
- 输入单词数组
words至少包含一个单词。
解题思路
步骤一：行的构建
首先，我们需要确定每行可以包含哪些单词。从当前索引开始，尽可能多地添加单词到当前行，直到添加下一个单词会使行长度超过 maxWidth。这个过程中，我们需要计算已包括的单词总长度加上必要的最小空格数（每两个单词之间至少一个空格）。
步骤二：计算空格
一旦确定了可以放在同一行的单词，接下来需要计算这些单词之间应分配多少空格：
- 非最后一行： 若行中有多于一个单词，需要将可用空格数（
maxWidth减去当前行单词字符总数）均匀分配到单词间隙中。如果空格数不能被均匀分配，多出的空格应从左到右依次分配。 - 最后一行： 单词之间只放一个空格，行尾用空格填充至
maxWidth。
步骤三：构建字符串
根据计算出的空格数构建每一行的字符串。对于非最后一行，每两个单词之间添加计算出的空格数。对于最后一行，单词之间添加一个空格，然后在行末添加足够的空格以达到 maxWidth。
代码实现
class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> result;
int n = words.size();
int index = 0;
while (index < n) {
// 确定当前行可以包含的单词数量。
int lineLength = words[index].size();
int last = index + 1;
while (last < n &&
lineLength + words[last].size() + 1 <= maxWidth) {
lineLength += words[last].size() + 1; // +1 是因为单词之间的空格
last++;
}
// 构建当前行。
string line = words[index];
int numWordsInLine = last - index;
// 如果是最后一行或者行中只有一个单词。
if (last == n || numWordsInLine == 1) {
for (int i = index + 1; i < last; i++) {
line += " " + words[i];
}
line += string(maxWidth - line.length(),
' '); // 填充行尾空格以满足最大宽度
} else {
// 不是最后一行并且行中有多个单词。
int totalSpaces =
maxWidth - (lineLength -
(numWordsInLine -
1)); // 减去在 lineLength 计算中已经计数的空格
int spacesBetweenWords = totalSpaces / (numWordsInLine - 1);
int extraSpaces = totalSpaces % (numWordsInLine - 1);
for (int i = index + 1; i < last; i++) {
int spacesToApply =
spacesBetweenWords + (i - index <= extraSpaces ? 1 : 0);
line += string(spacesToApply, ' ') + words[i];
}
}
result.push_back(line);
index = last;
}
return result;
}
};
