LeetCode 68. 文本左右对齐

◎

本节目标

先贪心确定每行单词，再用商和余数精确分配空格。

这道题是字符串综合中的格式构造母题。稳定做法分成两步：先决定一行放哪些单词，再根据行类型分配空格。

查看原题

题意与约束

给定单词数组和固定宽度 maxWidth，依次装入每行并返回排版结果。普通行需要左右对齐，多余空格优先放在左侧间隙；最后一行左对齐，单词之间只有一个空格。

每个输入单词长度都不超过行宽。

先选词，再排版

从 start 开始向右加入单词。若当前单词总字符数为 letters，准备加入第 end 个单词时，至少还需要 end - start 个单空格。因此判断式是：

letters + len(words[end]) + end - start <= maxWidth

一旦再加入一个单词会超宽，区间 [start, end) 就是当前行的完整单词集合。

空格的商与余数

普通行若有 gaps 个间隙，需要分配 maxWidth - letters 个空格：

• 每个间隙至少获得 totalSpaces / gaps 个；
• 余下 totalSpaces % gaps 个，从左到右每个间隙再获得一个。

最后一行或只有一个单词的行不做这种分配：用单空格连接，再在右侧补齐。

代码实现

两种语言都让“选词”循环只计算边界，让“排版”分支只构造已经确定的当前行。测试同时检查文本内容和每行精确宽度。

C++

C++17

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> answer;
        int start = 0;

        while (start < static_cast<int>(words.size())) {
            int end = start;
            int letters = 0;
            while (
                end < static_cast<int>(words.size()) &&
                letters + static_cast<int>(words[end].size()) + end - start <=
                    maxWidth
            ) {
                letters += static_cast<int>(words[end].size());
                end++;
            }

            int gaps = end - start - 1;
            string line;
            if (end == static_cast<int>(words.size()) || gaps == 0) {
                for (int index = start; index < end; index++) {
                    if (index > start) {
                        line += ' ';
                    }
                    line += words[index];
                }
                line += string(maxWidth - static_cast<int>(line.size()), ' ');
            } else {
                int totalSpaces = maxWidth - letters;
                int spacesPerGap = totalSpaces / gaps;
                int extraSpaces = totalSpaces % gaps;
                for (int index = start; index < end; index++) {
                    line += words[index];
                    if (index < end - 1) {
                        int spaces = spacesPerGap;
                        if (index - start < extraSpaces) {
                            spaces++;
                        }
                        line += string(spaces, ' ');
                    }
                }
            }

            answer.push_back(line);
            start = end;
        }

        return answer;
    }
};

Python

Python 3

class Solution:
    def fullJustify(self, words: list[str], maxWidth: int) -> list[str]:
        answer = []
        start = 0

        while start < len(words):
            end = start
            letters = 0
            while (
                end < len(words)
                and letters + len(words[end]) + end - start <= maxWidth
            ):
                letters += len(words[end])
                end += 1

            gaps = end - start - 1
            if end == len(words) or gaps == 0:
                line = " ".join(words[start:end])
                line += " " * (maxWidth - len(line))
            else:
                total_spaces = maxWidth - letters
                spaces_per_gap, extra_spaces = divmod(total_spaces, gaps)
                parts = []
                for index in range(start, end - 1):
                    spaces = spaces_per_gap
                    if index - start < extra_spaces:
                        spaces += 1
                    parts.append(words[index] + " " * spaces)
                parts.append(words[end - 1])
                line = "".join(parts)

            answer.append(line)
            start = end

        return answer

复杂度分析

设最终输出包含 C 个字符。每个单词只被选入和写出一次，空格也只在构造答案时写入，因此时间复杂度为 O(C)。返回结果占用 O(C) 空间；除答案外的额外空间为单行构造所需的 O(maxWidth)。

易错点

• 只计算单词字符数，忘记单词之间至少需要一个空格。
• 把余数空格分给右侧间隙。
• 对最后一行继续执行两端对齐。
• gaps == 0 时仍做除法。
• 边选词边补空格，导致边界和格式规则互相干扰。

模式迁移

“先确定分组，再分配剩余量”可以迁移到分页、分栏和批处理布局。若题目要求余量优先给前面的组，就使用商和余数；若要求居中或右对齐，只需替换余数的分配方向。