68. 文本左右对齐
题目描述
输入单词数组 words 和行宽 maxWidth。把单词按原顺序排成若干行，返回每一行组成的字符串数组。每行的长度必须恰好是 maxWidth。
分行时采用贪心：每行在放得下的前提下尽量多放单词，同一行相邻单词之间至少隔一个空格。
除最后一行外，每行都要两端对齐：第一个单词贴左边，最后一个单词贴右边，补足长度所需的空格分到各个单词间隙里。空格要尽量平均；分不均时，靠左的间隙比靠右的多。
如果某行只有一个单词，就让它靠左，右边用空格补满。最后一行也靠左：单词之间只隔一个空格，剩下的空格全补在行尾。
单词指不含空格的字符序列。每个单词长度在 1 到 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" 后补空格，而不是把空格放在两个单词中间。
示例 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 "]
解释：例如第一行三个间隙共 5 个空格，分配为 2、2、1，靠左的间隙多分。
数据范围
1 <= words.length <= 3001 <= words[i].length <= 20words[i]由小写英文字母和符号组成。1 <= maxWidth <= 100words[i].length <= maxWidth
解题思路
逐行贪心：从 words[i] 开始不断尝试放入下一个单词，条件是“已放单词总长 + 单词间至少一个空格 + 新单词长度 <= maxWidth”。放不下就确定这一行是 words[i:j]。若是最后一行或只有一个单词，用单空格连接再在右边补齐；否则把剩余空格 maxWidth - width 用 divmod 分给 gaps 个间隙，前 extra 个间隙各多 1 个。
为什么正确
width 始终是当前行已选单词的字母总数，(j - i) 是它们之间至少需要的空格数，二者之和不超过 maxWidth。
复杂度分析
时间 O(总字符数)，每个单词只被装入一次；除答案外额外空间 O(maxWidth)。
易错点
最后一行和只有一个单词的行不能平均分配空格，必须左对齐；另外 gaps=0 时不能做除法。分不均时多出的空格要给左边的间隙。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
res, i, n = [], 0, len(words)
while i < n:
j, width = i, 0
while j < n and width + len(words[j]) + (j - i) <= maxWidth:
width += len(words[j])
j += 1
gaps = j - i - 1
if j == n or gaps == 0:
line = ' '.join(words[i:j])
res.append(line + ' ' * (maxWidth - len(line)))
else:
space, extra = divmod(maxWidth - width, gaps)
line = ''
for k in range(i, j - 1):
line += words[k] + ' ' * (space + (1 if k - i < extra else 0))
res.append(line + words[j - 1])
i = j
return resclass Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> res = new ArrayList<>();
int i = 0, n = words.length;
while (i < n) {
int j = i, width = 0;
while (j < n && width + words[j].length() + (j - i) <= maxWidth) {
width += words[j].length();
j++;
}
int gaps = j - i - 1;
if (j == n || gaps == 0) {
String line = String.join(" ", Arrays.copyOfRange(words, i, j));
res.add(line + " ".repeat(maxWidth - line.length()));
} else {
int space = (maxWidth - width) / gaps, extra = (maxWidth - width) % gaps;
StringBuilder line = new StringBuilder();
for (int k = i; k < j - 1; k++) {
line.append(words[k]).append(" ".repeat(space + (k - i < extra ? 1 : 0)));
}
res.add(line + words[j - 1]);
}
i = j;
}
return res;
}
}class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> res;
int i = 0, n = words.size();
while (i < n) {
int j = i, width = 0;
while (j < n && width + (int)words[j].size() + (j - i) <= maxWidth) {
width += words[j].size();
j++;
}
int gaps = j - i - 1;
if (j == n || gaps == 0) {
string line = words[i];
for (int k = i + 1; k < j; k++) {
line += " " + words[k];
}
res.push_back(line + string(maxWidth - line.size(), ' '));
} else {
int space = (maxWidth - width) / gaps, extra = (maxWidth - width) % gaps;
string line = "";
for (int k = i; k < j - 1; k++) {
line += words[k] + string(space + (k - i < extra ? 1 : 0), ' ');
}
res.push_back(line + words[j - 1]);
}
i = j;
}
return res;
}
};func fullJustify(words []string, maxWidth int) []string {
res, i, n := []string{}, 0, len(words)
for i < n {
j, width := i, 0
for j < n && width+len(words[j])+(j-i) <= maxWidth {
width += len(words[j])
j++
}
gaps := j - i - 1
if j == n || gaps == 0 {
line := strings.Join(words[i:j], " ")
res = append(res, line+strings.Repeat(" ", maxWidth-len(line)))
} else {
space, extra := (maxWidth-width)/gaps, (maxWidth-width)%gaps
line := ""
for k := i; k < j-1; k++ {
pad := space
if k-i < extra {
pad++
}
line += words[k] + strings.Repeat(" ", pad)
}
res = append(res, line+words[j-1])
}
i = j
}
return res
}var fullJustify = function(words, maxWidth) {
const res = [];
let i = 0, n = words.length;
while (i < n) {
let j = i, width = 0;
while (j < n && width + words[j].length + (j - i) <= maxWidth) {
width += words[j].length;
j++;
}
const gaps = j - i - 1;
if (j === n || gaps === 0) {
const line = words.slice(i, j).join(' ');
res.push(line + ' '.repeat(maxWidth - line.length));
} else {
const space = Math.floor((maxWidth - width) / gaps), extra = (maxWidth - width) % gaps;
let line = '';
for (let k = i; k < j - 1; k++) {
line += words[k] + ' '.repeat(space + (k - i < extra ? 1 : 0));
}
res.push(line + words[j - 1]);
}
i = j;
}
return res;
};function fullJustify(words: string[], maxWidth: number): string[] {
const res: string[] = [];
let i = 0, n = words.length;
while (i < n) {
let j = i, width = 0;
while (j < n && width + words[j].length + (j - i) <= maxWidth) {
width += words[j].length;
j++;
}
const gaps = j - i - 1;
if (j === n || gaps === 0) {
const line = words.slice(i, j).join(' ');
res.push(line + ' '.repeat(maxWidth - line.length));
} else {
const space = Math.floor((maxWidth - width) / gaps), extra = (maxWidth - width) % gaps;
let line = '';
for (let k = i; k < j - 1; k++) {
line += words[k] + ' '.repeat(space + (k - i < extra ? 1 : 0));
}
res.push(line + words[j - 1]);
}
i = j;
}
return res;
}