Text Justification

68. 文本左右对齐

分析

分组单词（贪心）：
- 用指针 i 表示当前行的起始单词，j 表示下一个单词
- 不断尝试加入下一个单词，直到超出 maxWidth
构建每一行：
- 左对齐（最后一行或只有一个单词）：单词之间加 1 个空格，末尾补空格
- 普通行：
  - 空格平均分配：空格总数 = maxWidth - 总单词长度
  - 多余空格优先分配到左侧。
  - 使用 std::string(n, ' ') 插入空格
更新索引：处理完当前行后，将 i 移动到下一行的起始单词

时间复杂度

遍历所有单词，每个单词最多被遍历两次（分组和拼接），时间复杂度 O(n)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62


class Solution
{
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth)
    {
        std::vector<std::string> res;  // 存储结果
        for (int i = 0; i < words.size(); ++i)
        {
            int j = i + 1;  // 下一个单词的索引
            int len = words[i].size();  // 当前行的总长度

            // 将尽可能多的单词放入当前行
            while (j < words.size() && len + 1 + words[j].size() <= maxWidth)
            {
                len += 1 + words[j].size();  // 单词加空格
                ++j;
            }

            std::string line;  // 构建当前行内容

            // 情况1：最后一行或当前行只有一个单词，左对齐
            if (j == i + 1 || j == words.size())
            {
                line += words[i];  // 加入第一个单词
                for (int k = i + 1; k < j; ++k)  // 后续单词前加空格
                    line += ' ' + words[k];

                // 补齐剩余空格
                while (line.size() < maxWidth)
                    line += ' ';
            }
            else
            {
                // 情况2：普通行（多单词，需均匀分配空格）
                int count = j - i - 1;  // 单词间隔数
                int space = maxWidth - len + count;  // 总空格数

                line += words[i];  // 加入第一个单词
                int k = 0;

                // 多余空格优先分配到左侧
                while (k < (space % count))
                {
                    line += std::string(space / count + 1, ' ') + words[i + k + 1];
                    ++k;
                }

                // 均匀分配剩余空格
                while (k < count)
                {
                    line += std::string(space / count, ' ') + words[i + k + 1];
                    ++k;
                }
            }

            res.push_back(line);  // 保存当前行
            i = j - 1;  // 更新索引，处理下一行
        }

        return res;
    }
};