【題目】

給定一個單詞數(shù)組 words 和一個長度 maxWidth 越庇，重新排版單詞罩锐，使其成為每行恰好有 maxWidth 個字符，且左右兩端對齊的文本卤唉。

你應(yīng)該使用 “貪心算法” 來放置給定的單詞涩惑；也就是說，盡可能多地往每行中放置單詞搬味。必要時可用空格 ' ' 填充境氢，使得每行恰好有 maxWidth 個字符。

要求盡可能均勻分配單詞間的空格數(shù)量碰纬。如果某一行單詞間的空格不能均勻分配萍聊，則左側(cè)放置的空格數(shù)要多于右側(cè)的空格數(shù)。

文本的最后一行應(yīng)為左對齊悦析，且單詞之間不插入額外的空格寿桨。

注意:

• 單詞是指由非空格字符組成的字符序列。
• 每個單詞的長度大于 0强戴，小于等于 maxWidth亭螟。
• 輸入單詞數(shù)組 words 至少包含一個單詞。

示例 1:

輸入: 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        "
]
解釋: 注意最后一行的格式應(yīng)為 "shall be    " 而不是 "shall     be",
     因?yàn)樽詈笠恍袘?yīng)為左對齊骑歹，而不是左右兩端對齊预烙。       
     第二行同樣為左對齊，這是因?yàn)檫@行只包含一個單詞道媚。

示例 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                  "
]

提示:

• 1 <= words.length <= 300
• 1 <= words[i].length <= 20
• words[i] 由小寫英文字母和符號組成
• 1 <= maxWidth <= 100
• words[i].length <= maxWidth

【題目解析】

解題方法

1. 單詞分組：根據(jù)maxWidth，將單詞分組最域，每組內(nèi)的單詞總長度加上必要的最小空格數(shù)（即組內(nèi)單詞數(shù)減1）不超過maxWidth谴分。

2. 空格分配：對于每一組單詞，計(jì)算除單詞外的剩余空格數(shù)镀脂，根據(jù)貪心算法原則分配空格：

   • 如果組內(nèi)只有一個單詞牺蹄，則該單詞后填充所有空格；
   • 如果組內(nèi)有多個單詞薄翅，則將空格盡可能均勻分配在單詞之間沙兰。如果不能均勻分配，則左側(cè)的空隙比右側(cè)的多翘魄。

3. 最后一行處理：最后一行的單詞左對齊鼎天，單詞之間只有一個空格，行末填充空格熟丸。

4. 構(gòu)建每一行：根據(jù)上述空格分配原則训措，構(gòu)建每一行的字符串伪节。

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        res, cur, num_of_letters = [], [], 0
        for w in words:
            # 如果加上新單詞后超過最大寬度光羞，處理當(dāng)前行
            if num_of_letters + len(w) + len(cur) > maxWidth:
                for i in range(maxWidth - num_of_letters):
                    # 盡量平均分配空格
                    cur[i % (len(cur) - 1 or 1)] += ' '
                res.append(''.join(cur))
                cur, num_of_letters = [], 0
            cur.append(w)
            num_of_letters += len(w)
        # 處理最后一行绩鸣，左對齊，單詞間只有一個空格
        return res + [' '.join(cur).ljust(maxWidth)]

執(zhí)行效率

image.png

【總結(jié)】

適用問題類型:

這種方法適用于文本格式化問題纱兑，特別是需要根據(jù)給定的寬度對一系列單詞進(jìn)行左右對齊排版的場景呀闻。除了編程競賽或算法面試題目外，實(shí)際應(yīng)用包括但不限于文檔編輯軟件的文本排版潜慎、網(wǎng)頁內(nèi)容的動態(tài)布局捡多、終端界面的信息顯示，以及任何需要根據(jù)特定寬度顯示文本內(nèi)容的軟件功能铐炫。

解決算法: 貪心算法 + 空格均勻分配

算法特點(diǎn):

• 貪心原則: 在每一行盡可能多地放置單詞垒手，直到加入下一個單詞會超出最大寬度限制。
• 均勻分配空格: 對于一行中的多個單詞倒信，空格盡可能均勻分配在單詞之間科贬。如果不能完全均勻分配，則讓行的左側(cè)部分比右側(cè)部分多一些空格鳖悠。
• 特殊處理最后一行: 最后一行單詞左對齊榜掌，單詞之間只有一個空格，且行末填充足夠的空格直到最大寬度乘综。

時間復(fù)雜度與空間復(fù)雜度:

• 時間復(fù)雜度: O(n)憎账，其中n是單詞的總數(shù)量。每個單詞至少被遍歷和處理一次以確定其在文本中的位置卡辰。
• 空間復(fù)雜度: O(m)胞皱，其中m是輸出列表中字符串的總數(shù)。需要額外的空間來存儲每行排版后的字符串看政。

實(shí)踐意義:

• 文本排版功能: 在文檔編輯器朴恳、網(wǎng)頁設(shè)計(jì)、終端界面設(shè)計(jì)等軟件開發(fā)領(lǐng)域允蚣，文本的格式化和排版是一項(xiàng)基本且重要的功能于颖。掌握這種算法能夠幫助開發(fā)者實(shí)現(xiàn)復(fù)雜的文本排版需求。
• 理解貪心算法應(yīng)用: 貪心算法是解決優(yōu)化問題的一種有效方法嚷兔。通過這個問題森渐，開發(fā)者可以深入理解貪心算法的思想及其在實(shí)際問題中的應(yīng)用。
• 提高編程能力: 實(shí)現(xiàn)文本左右對齊的算法需要處理字符串冒晰、數(shù)組等數(shù)據(jù)結(jié)構(gòu)同衣，并涉及細(xì)節(jié)的控制和邊界情況的處理，是提高編程能力的好機(jī)會壶运。
• 增強(qiáng)算法設(shè)計(jì)能力: 設(shè)計(jì)一個既能滿足左右對齊又能優(yōu)雅處理最后一行特殊情況的算法耐齐，能夠鍛煉開發(fā)者的算法設(shè)計(jì)能力和解決復(fù)雜問題的能力。

題目鏈接

文本左右對齊