面试经典150题[024]：文本左右对齐（LeetCode 68）-EW帮帮网

文本左右对齐（LeetCode 68）

题目链接：文本左右对齐（LeetCode 68）
难度：困难

1. 题目描述

给定一个单词数组 words 和一个长度 maxWidth，重新排版单词，使每行恰好有 maxWidth 个字符，且左右两端对齐。使用贪心算法，尽可能多地往每行放置单词，必要时用空格填充。单词间空格尽可能均匀分配，左侧空格多于右侧。最后一行左对齐，单词间仅一个空格。

要求：

单词由非空格字符组成。
每个单词长度大于 0，小于等于 maxWidth。
数组至少包含一个单词。
1 <= words.length <= 300
1 <= words[i].length <= 20
1 <= maxWidth <= 100

示例：

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

2. 问题分析

2.1 规律

每行需恰好 maxWidth 个字符，包含单词和空格。
贪心策略：每行尽量多放单词，直到放不下为止。
普通行：左右对齐，空格均匀分配，左侧优先。
最后一行：左对齐，单词间仅一个空格，末尾补空格。
特殊情况：单单词行直接左对齐，末尾补空格。

2.2 贪心思路

分组单词：
- 遍历 words，用贪心算法确定每行能放的单词。
- 记录当前行起始单词索引 start 和单词数 word_count。
- 计算当前行单词总长度和最小空格需求（单词间至少一个空格）。
- 如果加入下一个单词后总长度（单词+最小空格）超过 maxWidth，则处理当前行。
格式化每行：
- 普通行：
  - 计算总空格数：maxWidth - 单词总长度。
  - 计算空格槽数（单词间隙数）：word_count - 1。
  - 若有多个单词，均匀分配空格，左侧优先（用除法和取模）。
  - 若只有一个单词，左对齐，末尾补空格。
- 最后一行：
  - 左对齐，单词间一个空格，末尾补空格。
处理逻辑：
- 用变量 i 遍历单词，curr_width 记录当前行单词总长度，word_count 记录单词数。
- 当无法加入更多单词或到达数组末尾时，处理当前行。
- 最后一行单独处理，确保左对齐。

2.3 示例

以 words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16 为例：

第一行：
- 单词：This, is, an（长度 4+2+2=8）
- 至少 2 个空格（2 个间隙），总长度 8+2=10 <= 16，可放入。
- 尝试加入 example（长度 7），总长度 8+7+3=18 > 16，停止。
- 空格数：16-8=8，间隙数：2，平均每间隙 8//2=4 空格。
- 输出：This is an
第二行：
- 单词：example, of, text（长度 7+2+4=13）
- 至少 2 个空格，总长度 13+2=15 <= 16，可放入。
- 尝试加入 justification.（长度 13），总长度 13+13+3=29 > 16，停止。
- 空格数：16-13=3，间隙数：2，左侧 2 空格，右侧 1 空格。
- 输出：example of text
最后一行：
- 单词：justification.（长度 13）
- 左对齐，末尾补空格。
- 输出：justification.

3. 代码实现

Python

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        result = []
        i = 0
        n = len(words)
        
        while i < n:
            # 确定当前行能放的单词
            word_count = 1
            curr_width = len(words[i])
            j = i + 1
            while j < n and curr_width + len(words[j]) + 1 <= maxWidth:
                curr_width += len(words[j]) + 1
                word_count += 1
                j += 1
            
            # 构建当前行
            line = []
            if j == n or word_count == 1:  # 最后一行或单单词行
                line.append(words[i])
                for k in range(i + 1, i + word_count):
                    line.append(" " + words[k])
                line = "".join(line)
                line += " " * (maxWidth - len(line))
            else:  # 普通行
                total_spaces = maxWidth - sum(len(words[k]) for k in range(i, i + word_count))
                gaps = word_count - 1
                if gaps == 0:  # 单单词
                    line = words[i] + " " * (maxWidth - len(words[i]))
                else:
                    spaces_per_gap = total_spaces // gaps
                    extra_spaces = total_spaces % gaps
                    for k in range(i, i + word_count):
                        line.append(words[k])
                        if k < i + word_count - 1:  # 不是最后一个单词
                            spaces = spaces_per_gap + (1 if k - i < extra_spaces else 0)
                            line.append(" " * spaces)
                    line = "".join(line)
            
            result.append(line)
            i += word_count
        
        return result

C++

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> result;
        int i = 0, n = words.size();
        
        while (i < n) {
            // 确定当前行能放的单词
            int word_count = 1;
            int curr_width = words[i].length();
            int j = i + 1;
            while (j < n && curr_width + words[j].length() + 1 <= maxWidth) {
                curr_width += words[j].length() + 1;
                word_count++;
                j++;
            }
            
            // 构建当前行
            string line;
            if (j == n || word_count == 1) {  // 最后一行或单单词行
                line = words[i];
                for (int k = i + 1; k < i + word_count; k++) {
                    line += " " + words[k];
                }
                line += string(maxWidth - line.length(), ' ');
            } else {  // 普通行
                int total_chars = 0;
                for (int k = i; k < i + word_count; k++) {
                    total_chars += words[k].length();
                }
                int total_spaces = maxWidth - total_chars;
                int gaps = word_count - 1;
                if (gaps == 0) {  // 单单词
                    line = words[i] + string(maxWidth - words[i].length(), ' ');
                } else {
                    int spaces_per_gap = total_spaces / gaps;
                    int extra_spaces = total_spaces % gaps;
                    for (int k = i; k < i + word_count; k++) {
                        line += words[k];
                        if (k < i + word_count - 1) {  // 不是最后一个单词
                            int spaces = spaces_per_gap + (k - i < extra_spaces ? 1 : 0);
                            line += string(spaces, ' ');
                        }
                    }
                }
            }
            
            result.push_back(line);
            i += word_count;
        }
        
        return result;
    }
};

4. 复杂度分析

时间复杂度：O(n)，其中 n 是单词数组长度。每个单词被处理一次，字符串构建为常数操作（因 maxWidth 较小）。
空间复杂度：O(n)，用于存储结果数组。临时变量（如 line）空间为 O(maxWidth)，为常数。

5. 总结

贪心策略：每行尽量多放单词，简化分组。
格式化关键：
- 普通行：均匀分配空格，左侧优先。
- 最后一行/单单词行：左对齐，末尾补空格。
注意点：
- 处理单单词行和最后一行需特殊逻辑。
- 空格分配用除法和取模实现左侧优先。

复习

面试经典150题[009]：跳跃游戏（LeetCode 55）
面试经典150题[010]：跳跃游戏 II（LeetCode 45）
面试经典150题[017]：罗马数字转整数（LeetCode 13）

面试经典150题[024]：文本左右对齐（LeetCode 68）