68. 文本左右对齐

1. 题目

给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

注意:

  • 单词是指由非空格字符组成的字符序列。
  • 每个单词的长度大于 0，小于等于 maxWidth。
  • 输入单词数组 words 至少包含一个单词。

示例 1:

1
2
3
4
5
6
7
输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
输出:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

示例 2:

1
2
3
4
5
6
7
8
9
10
输入:words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
输出:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
     因为最后一行应为左对齐，而不是左右两端对齐。       
     第二行同样为左对齐，这是因为这行只包含一个单词。

示例 3:

1
2
3
4
5
6
7
8
9
10
输入:words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]，maxWidth = 20
输出:
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]

提示:

  • 1 <= words.length <= 300
  • 1 <= words[i].length <= 20
  • words[i] 由小写英文字母和符号组成
  • 1 <= maxWidth <= 100
  • words[i].length <= maxWidth

2. 思路

  • 已知题目关键规则为以下：

    • [1] 尽可能在每一行中放置多的单词
    • [2] 单词A与单词B之间至少存在1个空格
    • [3] 文本的最后一行应当是左对齐，最后一行单词之间不存在额外的空格
    • [4] 应当尽可能地分配单词之间的空格数量，如果一行单词之间的空格不能平均分配，则左侧放置的空格数要多于右侧的空格数
    • [5] 每个单词的长度大于 0，小于等于 maxWidth

  • 初始化下标，遍历words数组，逐位移动下标，将满足maxWidth范围内的字符串下标进行记录

  • 确定要写入行的单词下标后，初始化perSpace变量用于记录每个单词后要跟的空格数量，同时判断即将写入该行的单词数量：

    • 如果写入该行的单词数量为1，则单词后要跟的空格数量perSpace值为maxWidth - 写入单词的长度
    • 如果写入该行的单词数量大于1，则单词后要跟的空格数量perSpace值为 (maxWidth - 写入单词的长度) / (单词数量 - 1)，计算得到平均分配的空格数量，其中单词数量 - 1是值2个单词中只需要1个空格占位

  • 继续计算additionalSpace，即是平均分配完空格后，多余的需要再次分配的空格

    • 如果写入该行的单词数量为1，则需要额外分配空格的值为0
    • 如果写入该行的单词数量大于1，则需要额外分配空格的值为maxWidth - (perSpace * (单词数量 - 1) + 写入单词的长度)

  • 在正式写入前，初始化变量lastLine，用于判断要写入的单词下标中是否包含了words数组的最后一位

  • 遍历上述提到的需要写入该行的单词下标，初始化str变量用于追加单词，并在完成遍历后，将该行写入结果集result中，在遍历过程中，需要判断：

    • 当写入的单词数量为1时，则直接追加余下所有空格
    • 当写入的单词不是该行的最后一个单词时，每个单词后都需要追加perSpace个空格
    • 当前行不是最后一行，同时additionalSpace值仍然大于0时，为了满足规则[3]和规则[4]，追加1个空格字符进str变量中，同时对additionalSpace进行减一，通过此操作达到平均分配，因为该数量为余数，肯定无法再完整分配完一轮，因此可以直接采用追加1个单位的空格字符
    • 当前行时最后一行，且已是最后一个单词时，则对该单词后进行剩余所有空白字符的填充，满足规则[3]左对齐

3. 代码

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
class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        var result = new ArrayList<String>();
        var index = 0;

        while (index < words.length) {
            var startIndex = index;
            var count = words[startIndex].length();
            var charCount = words[startIndex].length();
            var endIndex = index;
            while (endIndex + 1 < words.length) {
                if (words[endIndex + 1].length() + count + 1 <= maxWidth) {
                    count += (words[endIndex + 1].length() + 1);
                    charCount += (words[endIndex + 1].length());
                    endIndex++;
                } else {
                    break;
                }
            }
            index = endIndex + 1;

            var str = new StringBuilder();
            var wordCount = endIndex - startIndex + 1;
            var perSpace = wordCount == 1 ? maxWidth - charCount : (maxWidth - charCount) / (wordCount - 1);
            var additionalSpace = wordCount == 1 ? 0 : maxWidth - (perSpace * (wordCount - 1) + charCount);
            var lastLine = endIndex + 1 == words.length;
            for (int i = startIndex, j = endIndex; i <= j; ++i) {
                str.append(words[i]);

                if (wordCount == 1) {
                    appendSpace(str, perSpace);
                    continue;
                }
                
                if (i != endIndex) {
                    appendSpace(str, lastLine ? 1 : perSpace);
                }

                if (!lastLine && additionalSpace > 0) {
                    appendSpace(str, 1);
                    additionalSpace--;
                }

                if (lastLine && i == endIndex) {
                    appendSpace(str, maxWidth - str.length());
                }
            }

            result.add(str.toString());
        }

        return result;
    }

    private void appendSpace(StringBuilder str, int spaceCount) {
        for (var i = 0; i < spaceCount; ++i) {
            str.append(' ');
        }
    }
}

4. 复杂度

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

image-20230808190024651