0068. Text Justification
========================
题目信息
--------
:题号: 0068. 文本左右对齐
:难度: Hard
:主题: 字符串、贪心、文本排版、商余分配
:原题: `LeetCode 0068 `_
:重点: 从逐个试放单词,推导到唯一行边界与商余空格分配
题目重述
--------
给定按顺序排列的单词数组 ``words`` 和正整数 ``maxWidth``,把所有单词排成若干行并返回结果。
每行字符串长度必须恰好为 ``maxWidth``,单词顺序不能改变,并且每行必须尽可能容纳更多单词。
除最后一行外,普通行需要两端对齐:
* 空格只放在相邻单词之间;
* 各间隔的空格数应尽量相等;
* 无法均分时,左侧间隔比右侧间隔多一个空格。
最后一行使用单个空格分隔单词,剩余空格全部补在末尾。若普通行只有一个单词,也把该单词放在
行首并在末尾补空格。
约束条件:
* ``1 <= words.length <= 300``;
* ``1 <= words[i].length <= 20``;
* ``words[i]`` 只包含英文字母和符号;
* ``1 <= maxWidth <= 100``;
* 每个单词的长度都不超过 ``maxWidth``。
自建示例
--------
.. code-block:: text
输入:words = ["a", "bb", "ccc", "dddd"], maxWidth = 11
输出:["a bb ccc", "dddd "]
第一行的单词字符总数为 6,需要分配 5 个空格。两个间隔分别得到 3 个和 2 个空格;最后一行
左对齐并在末尾补空格。
.. code-block:: text
输入:words = ["one", "two", "three"], maxWidth = 7
输出:["one two", "three "]
前两个单词连同一个最小间隔恰好占满第一行。最后一个单词独占末行,右侧补两个空格。
.. code-block:: text
输入:words = ["abcdefgh", "i", "j"], maxWidth = 8
输出:["abcdefgh", "i j "]
第一个单词已经占满整行。末行使用单个空格连接 ``i`` 和 ``j``,其余位置补空格。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
std::string formatLine(
const std::vector& words,
int start,
int end,
int letters,
int width,
bool isLast
) {
const int count = end - start;
std::string line;
line.reserve(width);
if (isLast || count == 1) {
for (int index = start; index < end; ++index) {
if (index > start) {
line.push_back(' ');
}
line += words[index];
}
line.append(width - static_cast(line.size()), ' ');
return line;
}
const int gaps = count - 1;
const int totalSpaces = width - letters;
const int baseSpaces = totalSpaces / gaps;
const int extraSpaces = totalSpaces % gaps;
for (int index = start; index < end; ++index) {
line += words[index];
if (index + 1 < end) {
const int gapIndex = index - start;
const int spaces = baseSpaces +
(gapIndex < extraSpaces ? 1 : 0);
line.append(spaces, ' ');
}
}
return line;
}
std::vector groupThenFormat(
const std::vector& words,
int width
) {
std::vector> groups;
std::vector current;
int letters = 0;
for (const std::string& word : words) {
const int minimumLength = letters +
static_cast(current.size()) +
static_cast(word.size());
if (!current.empty() && minimumLength > width) {
groups.push_back(current);
current.clear();
letters = 0;
}
current.push_back(word);
letters += static_cast(word.size());
}
groups.push_back(current);
std::vector result;
result.reserve(groups.size());
for (int lineIndex = 0;
lineIndex < static_cast(groups.size());
++lineIndex) {
int groupLetters = 0;
for (const std::string& word : groups[lineIndex]) {
groupLetters += static_cast(word.size());
}
const bool isLast =
lineIndex + 1 == static_cast(groups.size());
result.push_back(formatLine(
groups[lineIndex],
0,
static_cast(groups[lineIndex].size()),
groupLetters,
width,
isLast
));
}
return result;
}
std::vector greedyWithFormatter(
const std::vector& words,
int width
) {
std::vector result;
int start = 0;
while (start < static_cast(words.size())) {
int end = start;
int letters = 0;
while (end < static_cast(words.size())) {
const int minimumLength = letters +
static_cast(words[end].size()) +
(end - start);
if (minimumLength > width) {
break;
}
letters += static_cast(words[end].size());
++end;
}
result.push_back(formatLine(
words,
start,
end,
letters,
width,
end == static_cast(words.size())
));
start = end;
}
return result;
}
public:
std::vector fullJustify(
std::vector& words,
int maxWidth
) {
return greedyWithFormatter(words, maxWidth);
}
};
题解
----
行边界搜索
~~~~~~~~~~
处理一行时,先只决定这一行包含哪些连续单词,不立即构造空格。设当前行候选区间为
``[start, end)``,其中单词字符总数为 ``letters``。
准备加入 ``words[end]`` 时,原有 ``end - start`` 个单词与新单词之间至少需要
``end - start`` 个单空格,因此加入后的最小长度为:
.. code-block:: text
letters + words[end].length + (end - start)
该值不超过 ``maxWidth`` 时,新单词可以进入当前行;首次超过宽度时,当前 ``end`` 就是唯一合法行尾。
最大装行不变量
~~~~~~~~~~~~~~
内层循环结束时,区间 ``[start, end)`` 满足两个条件:
* 区间内全部单词使用最少间隔时能够放入当前行;
* 若仍有下一个单词,把它加入后即使每个间隔只放一个空格也会超宽。
题目要求保持顺序并尽可能多装单词。仍可容纳时提前换行会违反要求;最少间隔已经超宽时,增加或重新分配
空格也无法容纳下一个单词。因此该贪心条件直接确定每一行的边界。
普通行空格分配
~~~~~~~~~~~~~~
普通行包含 ``count`` 个单词,共有 ``gaps = count - 1`` 个间隔。单词字符总数为 ``letters``,所以必须分配:
.. code-block:: text
totalSpaces = maxWidth - letters
对总空格数做商余分解:
.. code-block:: text
baseSpaces = totalSpaces / gaps
extraSpaces = totalSpaces % gaps
每个间隔先获得 ``baseSpaces`` 个空格,最左侧的 ``extraSpaces`` 个间隔再各获得一个。这样所有间隔
只可能相差一个空格,并且较多的空格全部位于左侧。
商余分配不变量
~~~~~~~~~~~~~~
以 ``a, bb, ccc`` 和宽度 11 为例:
.. list-table::
:header-rows: 1
* - 项目
- 数值
* - 单词字符数
- ``1 + 2 + 3 = 6``
* - 空格总数
- ``11 - 6 = 5``
* - 间隔数
- 2
* - 商与余数
- ``baseSpaces = 2``、``extraSpaces = 1``
* - 最终间隔
- 3 个空格、2 个空格
因为 ``totalSpaces = baseSpaces * gaps + extraSpaces``,全部空格都会被使用且不会重复。前
``extraSpaces`` 个间隔多放一个空格,正好实现左侧优先。
末行与独占行
~~~~~~~~~~~~
最后一行不参与商余分配。它先用单个空格连接单词,再把剩余空格全部补到末尾。
只有一个单词的普通行也采用相同格式。此时 ``gaps`` 为 0,没有可分配的单词间隔;把单词放在左侧并在
末尾补满,是满足固定宽度的唯一形式。统一处理这两类行也避免了除以零。
状态演化
~~~~~~~~
以 ``words = ["a", "bb", "ccc", "dddd"]``、``maxWidth = 11`` 为例:
.. list-table::
:header-rows: 1
* - 尝试加入
- 最小长度
- 结果
* - ``a``
- 1
- 加入第一行
* - ``bb``
- ``1 + 2 + 1 = 4``
- 加入第一行
* - ``ccc``
- ``3 + 3 + 2 = 8``
- 加入第一行
* - ``dddd``
- ``6 + 4 + 3 = 13``
- 超宽,结束第一行
第一行随后把 5 个空格分成 3 和 2,得到 ``"a bb ccc"``。第二行是末行,生成
``"dddd "``。
两种组织方式
~~~~~~~~~~~~
``groupThenFormat`` 先把所有行保存为二维单词数组,再逐行计算字符数和格式。这一版把分组与输出完全分开,
便于直接观察每行的单词集合,但会复制全部单词并保存中间分组。
``greedyWithFormatter`` 只维护当前行的起止下标和字符数。行边界确定后立即调用 ``formatLine``,不保存全部
中间分组。公开入口采用这一版,因为它保留相同的贪心逻辑,同时减少中间状态。
复杂度分析
~~~~~~~~~~
设全部单词字符数为 ``C``,输出行数为 ``L``。主方法每个单词在选行和格式化阶段各访问常数次,并写出
``L * maxWidth`` 个输出字符,因此时间复杂度为 ``O(C + L * maxWidth)``。
返回结果本身需要 ``O(L * maxWidth)`` 空间。除返回结果和当前正在构造的一行外,主方法只维护常数个下标与
计数,额外工作空间为 ``O(maxWidth)``。先分组方案还需要复制全部单词,额外空间为 ``O(C)``。
边界处理
~~~~~~~~
* 单个单词长度恰好等于 ``maxWidth`` 时,该行不需要补空格;
* 普通行只有一个单词时,直接在右侧补满,避免 ``gaps = 0`` 的除法;
* 最后一行始终使用单空格连接,不执行两端对齐;
* 下一单词无法放入当前行时,当前行至少已有一个单词,因为每个单词长度都不超过 ``maxWidth``;
* 普通行写入的字符数为 ``letters + totalSpaces``,左对齐行补到 ``maxWidth``,所有输出行长度均精确。