今天是紀錄LeetCode解題的第六十八天
是一題困難題
第六十八題題目：Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left-justified, and no extra space is inserted between words.

Note:

• A word is defined as a character sequence consisting of non-space characters only.
• Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.
• The input array words contains at least one word.

給定一個字串數組words和一個寬度maxWidth，格式化文本，使每行恰好包含maxWidth個字符，並且完全(左對齊和右對齊)

應該採用「貪婪」的排版方式，即每行盡可能塞入單字，必要時添加空格' '，使每行正好包含maxWidth個字元

單字之間的空格應盡可能均勻分佈，如果一行空格數不能被單字數整除，則左側的空格數應比右側空格數多

最後一行文字應該左對齊，單字之間不要插入額外的空格

注意：

• 單字的定義是僅由非空格字元組成的字元序列
• 每個單字的長度保證大於0且不超過maxWidth
• 輸入數組words至少包含一個單字

解題思路

遍歷words，每一次都去計算目前字的總長度 + 空格長度 + 下一個字的長度是否超出maxWidth，如果沒有則把當前的word加入line_word，超出的話就代表目前該行能塞入的單字已經滿了，那就開始對齊該行

首先判斷是否是最後一行或是只有一個單字都直接進行左對齊，其餘按照規則進行對齊

1. 計算需要分配的總空格數：total_spaces = maxWidth - line_len
2. 計算字之間的間隔：gaps = len(line_word) - 1
3. 計算每個間隔可以放置多少空格：space = total_spaces // gaps
4. 計算如果無法整除分配會多幾個空格：extra = total_spaces % gaps
5. 最後跑gaps次迴圈，每次將單字串接並且後面加上space個空格，如果有額外extra個空格，則當i < extra時加入空格到單字後面

程式碼

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        res = []
        line_word = [] #當前行的字
        line_len = 0   #當前行的總長度(不包含空格)
        for word in words:
            if line_len + len(line_word) + len(word) > maxWidth: #字的總長度 + 空格長度 + 下一個字的長度(看可不可以加入)
                res.append(justify(line_word,line_len,maxWidth,False)) #如果下一個字不能加入就按照規則對齊文字
                line_word = [] #對齊完文字之後清除該行準備下一行
                line_len = 0
            line_word.append(word) #如果還能加入下一個字執行這裡把文字加入
            line_len += len(word)
        res.append(justify(line_word,line_len,maxWidth,True))
        return res
def justify(line_word,line_len,maxWidth,is_last_line):
    if is_last_line or len(line_word) == 1: #最後一行或只有一個字，左對齊
        line = ' '.join(line_word)
        return line + ' ' * (maxWidth - len(line))
    else:
        total_spaces = maxWidth - line_len #需要分配的總空格數
        gaps = len(line_word) - 1 #字之間的間隔(有3個單字間隔為2)
        space = total_spaces // gaps
        extra = total_spaces % gaps #space為每個間隔的空格數 extra為無法整除分配所有空格時，多出來的空格數
        line = ''
        for i in range(gaps):
            line += line_word[i]
            line += ' ' * space #每個間隔先平均放空格數
            if i < extra: #從左邊放置多出來的空格
                line += ' '
        line += line_word[-1] #記得加最後一個字
        return line

執行過程

初始狀態

• words = ["This" , "is" , "an" , "example" , "of" , "text" , "justification."]
• maxWidth = 16
• res = []
• line_word = []
• line_len = 0

word = "This"

• if line_len + len(line_word) + len(word) > maxWidth → 0 + 0 + 4 > 16 → False
• line_word.append(word) → line_word = ["This"]
• line_len += len(word) → line_len = 4

word = "is"

• if line_len + len(line_word) + len(word) > maxWidth → 4 + 1 + 2 > 16 → False
• line_word.append(word) → line_word = ["This" , "is"]
• line_len += len(word) → line_len = 6

word = "an"

• if line_len + len(line_word) + len(word) > maxWidth → 6 + 2 + 2 > 16 → False
• line_word.append(word) → line_word = ["This" , "is" , "an"]
• line_len += len(word) → line_len = 8

word = "example"

• if line_len + len(line_word) + len(word) > maxWidth → 8 + 3 + 7 > 16 → True
• res.append(justify(line_word,line_len,maxWidth,False))

對齊(line_word = ["This","is","an"]、line_len = 8、maxWidth = 16、is_last_line = False)

• if is_last_line or len(line_word) == 1 → False
• total_spaces = maxWidth - line_len → 16 - 8 = 8
• gaps = len(line_word) - 1 → 3 - 1 = 2
• space = total_spaces // gaps → 8 // 2 = 4
• extra = total_spaces % gaps → 8 % 2 = 0
• line = ''

i = 0(以下空白以 _ 代替)

• line += line_word[i] → line = "This"
• line += ' ' * space → line = "This____"
• if i < extra → False

i = 1

• line += line_word[i] → line = "This____is"
• line += ' ' * space → line = "This____is____"
• if i < extra → False

跳出迴圈把最後一個單字加入

• line += line_word[i] → line = "This____is____an"

• res = ["This____is____an"]
• line_word = []
• line_len = 0
• line_word.append(word) → line_word = ["example"]
• line_len += len(word) → line_len = 7

word = "of"

• if line_len + len(line_word) + len(word) > maxWidth → 7 + 1 + 2 > 16 → False
• line_word.append(word) → line_word = ["example" , "of"]
• line_len += len(word) → line_len = 9

word = "text"

• if line_len + len(line_word) + len(word) > maxWidth → 9 + 2 + 4 > 16 → False
• line_word.append(word) → line_word = ["example" , "of" , "text"]
• line_len += len(word) → line_len = 13

word = "justification."

• if line_len + len(line_word) + len(word) > maxWidth → 9 + 2 + 14 > 16 →True
• res.append(justify(line_word,line_len,maxWidth,False))

對齊(line_word = ["example" , "of" , "text"]、line_len = 13、maxWidth = 16、is_last_line = False)

• if is_last_line or len(line_word) == 1 → False
• total_spaces = maxWidth - line_len → 16 - 13 = 3
• gaps = len(line_word) - 1 → 3 - 1 = 2
• space = total_spaces // gaps → 3 // 2 = 1
• extra = total_spaces % gaps → 3 % 2 = 1
• line = ''

i = 0

• line += line_word[i] → line = "example"
• line += ' ' * space → line = "example_"
• if i < extra → True
• line += ' ' → line = "example__"

i = 1

• line += line_word[i] → line = "example__of"
• line += ' ' * space → line = "example__of_"
• if i < extra → False

跳出迴圈把最後一個單字加入

• line += line_word[i] → line = "example__of_text"

• res = ["This____is____an" , "example__of_text"]
• line_word = []
• line_len = 0
• line_word.append(word) → line_word = ["justification."]
• line_len += len(word) → line_len = 14

• res.append(justify(line_word,line_len,maxWidth,True))

對齊(line_word = ["justification."]、line_len = 14、maxWidth = 16、is_last_line = True)

• if is_last_line or len(line_word) == 1 → True
• line = ' '.join(line_word) → line = "justification."
• return line + ' ' * (maxWidth - len(line)) → line = "justification.__"

• res = ["This____is____an" , "example__of_text" , "justification.__"]
• return res