LeetCode 68. 文本左右对齐（难）

算法实现效果类似Word中文本左右对齐功能，使用了贪心算法。

题目

给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。

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

示例

示例:

1
2
3
4
5
6
7
8
9
输入:
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
输入:
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
11
12
13
输入:
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、两个单词之间至少有一个空格，如果单词加空格长度超过maxWidth，说明该单词放不下,比如示例1：当我们保证this is an 再加入example变成this is an example总长度超过maxWidth,所以这一行只能放下this is an 这三个单词。
2、this is an长度小于maxWidth，考虑分配空格，当不能保证每个间隔的空格数目一样多的时候，多出来的空格从左往右依次向每个间隔添加1个，靠近右边的一部分空格，可能就添加不上了，这样一来就保证了左边空格数大于右边的。
3、最后一行，要尽量靠左,例如示例2的："shall be "。

我们针对上面三个问题，有如下解决方案：
1、先找到一行最多可以容下几个单词
2、分配空格，例如this is an ，对于宽度为maxWidth，我们可以用space_count = maxWidth - all_word_len 计算出剩余的空格，然后用 average_space = space_count // (word_count - 1) 计算出平均每个间隔应该有多少个空格。接着，用 remaind_count = space_count % (word_count - 1) 计算出多出来的空格。最后将这些多出来的空格从左往右依次向每个间隔添加1个。
3、针对最后一行单独考虑，最后一行肯定不足maxWidth，但是最后一行应为左对齐 且单词之间不插入额外的空格，这里需要单独写代码实现。

Python版本

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        res = []
        selected_words = []
        selected_count = 0
        remaind_words = words[:]
        for word in words:
            # 没超出就说明这次可以选择
            if selected_count + len(selected_words) + len(word) <= maxWidth:
                selected_count += len(word)
                selected_words.append(word)
            # 否则说明超出了maxWidth 生成一行
            else:
                if len(selected_words) < 2:
                    res.append("{}{}".format(selected_words[0], " "*(maxWidth-len(selected_words[0]))))
                    remaind_words.remove(selected_words[0])
                else:
                    # 计算空格数
                    space_count = maxWidth - selected_count
                    intervel_count = space_count // (len(selected_words) - 1)
                    space_list = [" " * intervel_count] * (len(selected_words) - 1)
                    remaind_count = space_count % (len(selected_words) - 1)
                    for i in range(remaind_count):
                        space_list[i] += " "
                    # 开始拼接
                    tmp_str = ""
                    for index in range(len(selected_words)):
                        selected_word = selected_words[index]
                        remaind_words.remove(selected_word)
                        space = space_list[index] if index < len(space_list) else ""
                        tmp_str += "{}{}".format(selected_word, space)
                    res.append(tmp_str)
                selected_count = len(word)
                selected_words = [word]
        
        # 特殊处理最后一行 最后一行应为左对齐 且单词之间不插入额外的空格
        if len(remaind_words) < 2:
            res.append("{}{}".format(remaind_words[0], " "*(maxWidth-len(remaind_words[0]))))
        else:
            remaind_words_count = 0
            for i in remaind_words:
                remaind_words_count += len(i)
            remaind_words_count += (len(remaind_words) - 1)
            res.append("{}{}".format(" ".join(remaind_words), " "*(maxWidth-remaind_words_count)))

        return res



Input = [
    ["This", "is", "an", "example", "of", "text", "justification."],
    ["What","must","be","acknowledgment","shall","be"],
    ["Science","is","what","we","understand","well","enough","to","explain", "to","a","computer.","Art","is","everything","else","we","do"]
]
Input1 = [16, 16, 20]
Answer = [
    [
    "This    is    an",
    "example  of text",
    "justification.  "
    ],
    [
    "What   must   be",
    "acknowledgment  ",
    "shall be        "
    ],
    [
    "Science  is  what we",
    "understand      well",
    "enough to explain to",
    "a  computer.  Art is",
    "everything  else  we",
    "do                  "
    ]
]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.fullJustify(Input[i], Input1[i])
        if reslut == Answer[i]:
            print(True)
        else:
            print(False)
            print(reslut)
            print(Answer[i])

时间复杂度： \(O(n)\)
执行用时 :44 ms, 在所有 Python3 提交中击败了27.39%的用户
内存消耗 :13.5 MB, 在所有 Python3 提交中击败了7.50%的用户

一个更简洁的写法

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
class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        res = []
        n = len(words)
        i = 0

        def one_row_words(i):
            # 至少 一行能放下一个单词, cur_row_len
            left = i
            cur_row_len = len(words[i])
            i += 1
            while i < n:
                # 当目前行 加上一个单词长度 再加一个空格
                if cur_row_len + len(words[i]) + 1 > maxWidth:
                    break
                cur_row_len += len(words[i]) + 1
                i += 1
            return left, i

        while i < n:
            left, i = one_row_words(i)
            # 该行几个单词获取
            one_row = words[left:i]
            # 如果是最后一行了
            if i == n :
                res.append(" ".join(one_row).ljust(maxWidth," "))
                break
            # 所有单词的长度
            all_word_len = sum(len(i) for i in one_row)
            # 至少空格个数
            space_num = i - left - 1
            # 可以为空格的位置
            remain_space = maxWidth - all_word_len
            # 单词之间至少几个空格,还剩几个空格没用
            if space_num:
                a, b = divmod(remain_space, space_num)
            # print(a,b)
            # 该行字符串拼接
            tmp = ""
            for word in one_row:
                if tmp:
                    tmp += " " * a
                    if b:
                        tmp += " "
                        b -= 1
                tmp += word
            #print(tmp, len(tmp))
            res.append(tmp.ljust(maxWidth, " "))
        return res

有效语法糖

1、Python divmod() 函数
python divmod() 函数把除数和余数运算结果结合起来，返回一个包含商和余数的元组(a // b, a % b)。
在 python 2.3 版本之前不允许处理复数。

1
2
3
4
5
6
>>>divmod(7, 2)
(3, 1)
>>> divmod(8, 2)
(4, 0)
>>> divmod(1+2j,1+0.5j)
((1+0j), 1.5j)

2、基于Python Set.difference() 的去重

1
2
3
4
5
>>> a = [1, 2, 3, 4, 5]
>>> b = [1, 2, 3, 8, 9]
>>> c = set(a).difference(set(b))
>>> c
{4, 5}

参考连接

LeetCode用户题解