在处理文档排版、开发富文本编辑器或构建命令行界面工具时，我们经常遇到一个非常经典且具有挑战性的问题：如何将一段文本根据指定的宽度进行完美的两端对齐？
这不仅仅是简单地添加空格，它涉及到单词的贪婪选择、空格的数学计算以及特殊情况的处理。在这篇文章中，我们将深入探讨这个问题的每一个细节，从核心思路到具体的代码实现，带你一步步编写出既高效又优雅的解决方案。我们将一起分析算法逻辑，处理边缘情况，并优化代码结构，确保你能彻底掌握这一技能。
问题描述：我们需要做什么？
假设给定一个单词数组 INLINECODEd3869367 和一个固定的行宽 INLINECODEd4002a3b。我们的目标是重新排列这些单词，使得每一行都恰好包含 W 个字符，并满足以下条件：
- 单词完整性：每个单词必须完整地放在一行中，不能被截断或拆分。
- 贪婪填充：每一行应尽可能多地包含单词，即如果下一个单词能放进去，就必须放进去。
- 左右对齐：除了最后一行外，其余行的左右两端都必须对齐。这意味着我们需要在单词之间插入额外的空格。
- 空格分配策略：如果一行中的空格无法均匀分配，请务必将多余的空格优先分配到左侧的间隔中。这是实现美观排版的关键。
- 最后一行特殊处理：最后一行应保持左对齐，单词之间只需保留一个标准空格，不足的部分用空格在末尾补齐。
实战示例分析
为了更直观地理解需求，让我们来看一个具体的例子。
输入：
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
让我们一步步模拟这个过程：
第一行：
我们尝试放入单词。
- "This" (4) + "is" (2) + "an" (2) = 8 个字符。
- 加上单词间默认的最小空格（2个空格），目前长度为 8 + 2 = 10。
- 下一个词是 "example" (7)。10 + 1 + 7 = 18，这超过了 maxWidth (16)。所以，"example" 不能放在第一行。
- 第一行选定的单词： ["This", "is", "an"]。
- 字符总数：4 + 2 + 2 = 8。
- 需要的空格总数：16 – 8 = 8。
- 间隔数：2个（"This"和"is"之间，"is"和"an"之间）。
- 基础空格：8 / 2 = 4。
- 额外空格：8 % 2 = 0。不需要额外的左侧空格。
- 结果：
"This is an"(每个间隔4个空格)。
第二行：
- 从 "example" 开始。
- "example" (7) + "of" (2) = 9。
- 加上默认空格：9 + 1 = 10。
- 下一个词 "text" (4)。10 + 1 + 4 = 15。依然 <= 16。放入！
- 下一个词 "justification." (14)。15 + 1 + 14 > 16。放不下了。
- 第二行选定的单词： ["example", "of", "text"]。
- 字符总数：7 + 2 + 4 = 13。
- 需要的空格总数：16 – 13 = 3。
- 间隔数：2个。
- 基础空格：3 / 2 = 1。
- 额外空格：3 % 2 = 1。第一个间隔获得这个额外的空格。
- 结果：
"example of text"（第一个间隔2个空格，第二个1个空格）。
第三行（最后一行）：
- 只剩下 ["justification."]。
- 规则：左对齐。
- 结果：
"justification. "（末尾补齐空格）。
算法核心思路
根据上述分析，我们可以将解决过程分解为两个主要阶段：
#### 第一阶段：贪婪选择单词
我们需要一个函数来决定一行能容纳哪些单词。这就像打包行李一样，能塞多少塞多少。我们计算当前行的字符长度，不断尝试加入下一个单词，直到加不下为止。注意，除了第一个单词外，每个单词前面至少需要一个空格。
#### 第二阶段：构建与对齐
选好单词后，我们需要构建字符串。这里分两种情况：
- 普通行：我们需要计算“总空格数”。公式为 INLINECODEea229099。然后，我们将这些空格分配到单词之间的 INLINECODE765a942f（间隔）中。遵循“左多右少”的原则。
- 最后一行：直接将单词用单个空格连接，然后在末尾补空格直到长度为 W。这通常是简单的字符串拼接操作。
C++ 代码实现与深度解析
现在，让我们将上述思路转化为代码。我们将代码分解为几个清晰的辅助函数，以提高可读性和模块化程度。
#### 1. 辅助函数：计算单词总长度
首先，我们需要一个快速计算某区间内单词字符总和的函数。注意，这不包括空格。
// 计算从索引 start 到 end 的所有单词的字符总长度
// 注意：这里只计算纯字符，不包括单词间的空格
int countCharacters(int start, int end, vector &arr) {
int cnt = 0;
for (int i = start; i <= end; i++) {
cnt += arr[i].length();
}
return cnt;
}
#### 2. 辅助函数：填充行尾空格
主要用于处理最后一行，或者只有一个单词的行（这种情况通常也是左对齐或者单词居左，剩余补空格，视具体需求而定，但在Text Justification中通常视作左对齐逻辑）。
// 在字符串末尾填充空格，使其长度达到 W
string padLine(string &str, int W) {
int len = str.length();
// 循环添加空格直到长度满足要求
for (int i = 0; i < W - len; i++) {
str.push_back(' ');
}
return str;
}
#### 3. 核心逻辑：一行文本的对齐
这是算法中最复杂的部分。它决定了单词之间如何分配空格。
// 核心函数：将索引 [start, end] 范围内的单词格式化为一行
string justify(int start, int end, vector &arr, int W) {
string justifiedLine = "";
int wordsCnt = end - start + 1; // 当前行的单词数量
// 特殊情况 1：如果该行只有一个单词，或者这是最后一行（稍后在主函数判断），
// 我们直接左对齐并填充空格。
if (wordsCnt == 1) {
return padLine(arr[start], W);
}
// 计算所有单词的纯字符总数
int totalCharLen = countCharacters(start, end, arr);
// 计算我们需要分配的总空格数
// 例如：宽度16，单词总长8，则需要分配8个空格
int spaceCnt = W - totalCharLen;
// 计算单词之间的间隔数量 (单词数 - 1)
int gaps = wordsCnt - 1;
// 计算每个间隙基础分配多少空格
string space = " ";
int baseSpaces = spaceCnt / gaps;
// 更新基础空格字符串
space = string(baseSpaces, ‘ ‘);
// 计算无法均分的余数（额外空格），这些将分配给左边的间隙
int extraSpaces = spaceCnt % gaps;
// 遍历单词进行拼接
for (int i = start; i <= end; i++) {
// 1. 添加单词本身
justifiedLine.append(arr[i]);
// 2. 如果不是最后一个单词，则添加空格
if (i 0) {
justifiedLine.push_back(‘ ‘);
extraSpaces -= 1;
}
}
}
return justifiedLine;
}
#### 4. 主函数：整合流程
现在，我们将所有部分串联起来。首先通过 getEnd 找出一行能放多少单词，然后判断是否是最后一行来决定调用哪种对齐逻辑。
// 贪婪算法：找出从 start 开始，最多能容纳单词的结束索引 end
int getEnd(int start, vector &arr, int W) {
int end = start + 1;
// 初始长度为第一个单词的长度
int len = arr[start].length();
// 尝试添加下一个单词
// 条件：不超过数组范围 且 (当前长度 + 1个空格 + 下一个单词长度 <= W)
while (end < arr.size() && (len + 1 + arr[end].length()) <= W) {
len += arr[end].length() + 1; // 更新长度：单词+1个空格
end += 1;
}
// end 最后指向的是不能放入的第一个单词，所以要减1
return end - 1;
}
vector solve(vector &arr, int W) {
vector result;
int n = arr.size();
int index = 0;
// 遍历所有单词
while (index < n) {
// 1. 找出当前行能容纳的单词结束位置
int end = getEnd(index, arr, W);
// 2. 判断是否是最后一行
if (end == n - 1) {
// 最后一行逻辑：单词间单空格，末尾填充
string lastLine = "";
for (int i = index; i <= end; i++) {
lastLine.append(arr[i]);
if (i < end) lastLine.push_back(' ');
}
// 调用填充函数
result.push_back(padLine(lastLine, W));
} else {
// 普通行逻辑：两端对齐
result.push_back(justify(index, end, arr, W));
}
// 3. 移动 index 到下一行的起始单词
index = end + 1;
}
return result;
}
常见错误与调试技巧
在实现这个算法时，你可能会遇到一些棘手的边缘情况。让我们看看如何避免它们：
1. 整数溢出风险
虽然在这个问题中 INLINECODE13b7bdff 通常不会特别大，但在计算字符长度时，如果数据量巨大，使用 INLINECODE04483ef7 可能会溢出。不过对于普通文本处理，int 是足够的。确保在累加长度时不要超过类型限制。
2. 只有一个单词的行
这是一个常见的测试用例陷阱。例如：INLINECODE7fbb2a93, INLINECODEe011852b。
- 错误做法：尝试计算空隙。此时
gaps = 0，会导致除以零错误。 - 正确做法：在 INLINECODEba6f3ba6 函数开头检查 INLINECODE115a47bd，直接调用
padLine左对齐。
3. 空格计算精度
当我们在计算 spaceCnt 时，必须仔细。
spaceCnt = W - countCharacters(start, end, arr)
一定要确保这是“剩余可用空间”，而不是单词原本带有的空间。我们假设单词进入行时是不带空格的，所有空格都由我们手动分配。
性能优化与最佳实践
时间复杂度分析：
我们的算法是线性的，记为 O(N)，其中 N 是所有单词字符的总数。getEnd 函数中的指针从未回退，每个单词只被访问常数次。
空间复杂度分析：
除了存储结果的字符串数组外，我们只使用了少量的临时变量。空间复杂度主要是结果集的大小，即 O(N)。
代码优化建议：
你可以尝试使用 INLINECODE7182af98 来构建字符串，这在某些 C++ 标准库实现中可能比反复调用 INLINECODE19828879 或 INLINECODE0c08c90b 更高效。此外，INLINECODE30a6eb4e 的构造函数支持 INLINECODE84f12fcd 形式（如 INLINECODEdbb4b514），这比循环添加空格要快得多且代码更简洁，我们在代码中已经使用了这一点。
总结
文本两端对齐虽然看起来是一个简单的字符串操作问题，但它完美地结合了贪婪算法的思想（如何选择单词）和数学模拟（如何分配空格）。通过将问题拆解为“选择单词”和“构建行”两个步骤，我们可以写出逻辑清晰、易于维护的代码。
当你下次在开发 Word 处理器、网页排版引擎或是编写漂亮的命令行工具时，你会发现这个算法非常有用。希望这篇文章不仅帮你解决了这个问题，还让你对处理字符串和边缘情况有了更深的理解。