LeetCode: 文本左右对齐

在软件开发和算法学习中，LeetCode 是一个广受欢迎的平台，它提供了大量的算法问题供开发者练习和提升自己的编程能力。其中，“文本左右对齐”（Text Justification）是一道具有挑战性的字符串处理问题，它要求我们将给定的单词数组按照指定的最大宽度进行格式化，使得每行文本的左右两端都对齐（除了最后一行）。本文将详细介绍这个问题的解决方案，包括问题分析、算法思路、代码实现以及复杂度分析。

目录#

  1. 问题描述
  2. 问题分析
  3. 算法思路
  4. 代码实现
  5. 复杂度分析
  6. 常见实践和最佳实践
  7. 示例用法
  8. 总结
  9. 参考资料

1. 问题描述#

给定一个单词数组 words 和一个最大宽度 maxWidth，将文本进行格式化，使得每行文本的长度恰好为 maxWidth，并且左右两端对齐（除了最后一行，最后一行左对齐）。具体要求如下：

  • 单词之间的空格应该尽可能均匀分布。
  • 如果无法均匀分布，多余的空格应该优先分配给左边的间隔。
  • 最后一行文本应该左对齐，并且单词之间只有一个空格。

示例：

输入:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
输出:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

2. 问题分析#

这个问题的关键在于如何将单词分组到不同的行中，并且合理地分配空格。具体步骤如下：

  • 分组：将单词按照每行最大宽度进行分组，确保每行的单词长度之和加上单词之间的空格长度不超过 maxWidth。
  • 分配空格：对于每行文本，根据单词数量和剩余空格数，计算每个间隔应该分配的空格数。对于最后一行，只需要在单词之间添加一个空格，剩余的空格填充在末尾。

3. 算法思路#

步骤：#

  1. 初始化变量：初始化一个空列表 result 用于存储最终的结果，以及 start 和 end 指针用于表示当前行的单词范围。
  2. 分组单词：遍历单词数组，将单词分组到不同的行中。对于每一行，计算单词长度之和 totalLength，并检查是否可以添加下一个单词。
  3. 分配空格：对于每一行，计算需要分配的空格数 spaceCount 和间隔数 gapCount。如果是最后一行或者只有一个单词，单词之间只需要一个空格，剩余的空格填充在末尾；否则，计算每个间隔的平均空格数 averageSpace 和多余的空格数 extraSpace，将多余的空格优先分配给左边的间隔。
  4. 构建每行文本：根据分配的空格数，构建每行文本，并添加到 result 列表中。

4. 代码实现#

def fullJustify(words, maxWidth):
    result = []
    start = 0
    while start < len(words):
        # 计算当前行可以容纳的单词
        end = start
        totalLength = len(words[start])
        while end + 1 < len(words) and totalLength + len(words[end + 1]) + (end - start + 1) <= maxWidth:
            end += 1
            totalLength += len(words[end])
 
        # 计算需要分配的空格数
        spaceCount = maxWidth - totalLength
        gapCount = end - start
        if end == len(words) - 1 or gapCount == 0:
            # 最后一行或者只有一个单词，左对齐
            line = ' '.join(words[start:end + 1])
            line += ' ' * (maxWidth - len(line))
        else:
            # 非最后一行，左右对齐
            averageSpace = spaceCount // gapCount
            extraSpace = spaceCount % gapCount
            line = ''
            for i in range(start, end):
                line += words[i]
                line += ' ' * (averageSpace + (1 if i - start < extraSpace else 0))
            line += words[end]
        result.append(line)
        start = end + 1
    return result

5. 复杂度分析#

  • 时间复杂度：O(n)O(n)，其中 nn 是单词数组的长度。我们只需要遍历一次单词数组，对于每个单词，处理时间是常数级的。
  • 空间复杂度：O(m)O(m)，其中 mm 是结果列表的长度。主要的空间开销是存储最终的结果。

6. 常见实践和最佳实践#

常见实践#

  • 使用指针：使用 start 和 end 指针来表示当前行的单词范围，方便分组和处理。
  • 数学计算：通过数学计算来分配空格，确保空格均匀分布。

最佳实践#

  • 边界条件处理：注意处理最后一行和只有一个单词的情况，这两种情况需要特殊处理。
  • 代码可读性：使用有意义的变量名和注释，提高代码的可读性。

7. 示例用法#

words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
result = fullJustify(words, maxWidth)
for line in result:
    print(line)

8. 总结#

“文本左右对齐”是一道具有挑战性的字符串处理问题，需要我们合理地分组单词并分配空格。通过使用指针和数学计算，我们可以高效地解决这个问题。在实现过程中，需要注意边界条件的处理，确保代码的正确性和可读性。

9. 参考资料#

2026-08