文本左右对齐

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

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

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

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

说明:

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

输入:
words = [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”]
maxWidth = 16
输出:
[
“This is an        ”,
“example of text”,
“justification.     ”
]
示例 2:

输入:
words = [“What”,”must”,”be”,”acknowledgment”,”shall”,”be”]
maxWidth = 16
输出:
[
“What must be      ”,
“acknowledgment “,
“shall be               ”
]
解释:

• 注意最后一行的格式应为 "shall be" 而不是 “shall be”,
• 因为最后一行应为左对齐，而不是左右两端对齐。
• 第二行同样为左对齐，这是因为这行只包含一个单词。

示例 3:

输入:
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                           ”
]
解题思路：
步骤一：找出每一个符合长度的组合
步骤二：对每一个符合条件的组合进行字符串整合（注意：一定要看清楚题目中的解释）

步骤的具体思路：
步骤一思路：使用 while 循环，来依次寻找符合条件的字符串组合，保证这一过程的时间复杂度为 O(n)，最好不要使用 for 循环，如果使用 for 循环会使得时间复杂度增大

步骤二思路：注意这里的间隔是尽可能的均分，同时在无法均分的时候，尽可能使相邻两个间隔的空格数差值最小，同时保证左边的空格数要比右边的大，所以我的思路时递归的类似思想（实现并非递归）。每一次循环进行均分判断，如果可以均分则直接均分剩余间隔，如果无法均分则剩余间隔最左间隔空格数 space_left = n // d + 1（n 此时需要填充的空格数，d 此时需要填充的间隔数）

贴我的代码：

def fullJustify(words, maxWidth):
    l = []
    i = 0
    while (i < len(words)):
        l.append([])
        t = -1  # 为方便计算假设第一个单词前也有空格，故总长度从-1计算
        while (i < len(words) and len(words[i]) + 1 + t <= maxWidth):
            l[-1].append(words[i])

            t = t + len(words[i]) + 1
            i = i + 1
    e = []
    for i in range(len(l) - 1):
        s = l[i][0]
        if (len(l[i])) == 1:  # 只有一个单词便只用空格填充
            s = s + (maxWidth - len(s)) * ' '
            e.append(s)
            continue
        else:
            t = sum(map(lambda x: len(x), l[i]))
            a = maxWidth - t  # 平分空格
            b = a // (len(l[i]) - 1)
            c = a % (len(l[i]) - 1)
            k = 1
            while (k <= c):
                s = s + ' ' * (b + 1) + l[i][k]
                k = k + 1
            while (k < len(l[i])):
                s = s + ' ' * b + l[i][k]
                k = k + 1
        e.append(s)
    s = l[-1][0]
    for i in range(1, len(l[-1])):
        s = s + ' ' + l[-1][i]
    s = s + (maxWidth - len(s)) * ' '
    e.append(s)
    print(e)
    return e

贴大神的代码：leetcode 上传代码后，超过 99% 的用户。

class Solution:
   def fullJustify(self, words: list, maxWidth: int) -> list:
       if not words:
           return words
       res = []
       sentence = words[0]
       has_word_num = 1    # 句子中已有词的数量
       for word in words[1:]:
           if len(sentence) + len(word) + 1 <= maxWidth:  # 句子再加一个词的长度和maxWidth比较
               sentence += ' ' + word
               has_word_num += 1
           else:  # 长度超过后，补全当前句子
               pad = maxWidth - len(sentence)  # 待补齐长度
               if has_word_num == 1:   # 如果只有一个词，则左对齐
                   sentence += pad*" "
               else:   # 否则，将多出来的长度，均匀分配给空格
                   quotient = pad//(has_word_num-1)  # has_word_num - 1代表空格个数。商：一个空格能分配的补齐长度
                   mod = pad % (has_word_num-1) #
                   pad_list = [quotient+1]*(has_word_num-1)  # pad_list中元素代表每一个位置词与词之间空格的个数，
                   for i in range(mod):
                       pad_list[i] += 1  # 多出来不能整除的余数，从第一个空格开始再依次分配一个。
                   sentence_list = sentence.split()
                   sentence = sentence_list[0]
                   for each_num,each_word in zip(pad_list,sentence_list[1:]):
                       sentence += each_num*" " + each_word  # 句子和词之间用each_num个空格隔开
               res.append(sentence)  # 当前句子加入结果中
               sentence = word  # 重新开始下一个句子
               has_word_num = 1
       if sentence:  # 如果最后句子还剩余，即最后一行，直接左对齐
           res.append(sentence+(maxWidth-len(sentence))*" ")
       print(res)
       return res

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