LeetCode 文本左右對齊：雙指針逐行填充空格

題目描述

給定單詞列表和行寬 maxWidth，將文本按左右對齊排版。每行盡可能多放單詞，單詞間至少一空格，多餘空格優先分配給左側間隙。最後一行左對齊，單詞間單空格。

雙指針逐行處理

用 start 和 end 確定當前行單詞範圍。計算單詞總長 wordLen，空格總數 spaces = maxWidth - wordLen。若只有一個單詞或為最後一行，左對齊；否則平均分配空格：每間隙 spaces / (cnt-1)，前 spaces % (cnt-1) 個間隙多一空格。

代碼實現 (Python)

class Solution:
    def fullJustify(self, words, maxWidth):
        res, start, wordLen = [], 0, 0
        for i, w in enumerate(words):
            if wordLen + len(w) + i - start > maxWidth:
                cnt = i - start
                if cnt == 1:
                    res.append(words[start] + ' ' * (maxWidth - wordLen))
                else:
                    spaces = maxWidth - wordLen
                    q, r = divmod(spaces, cnt - 1)
                    for j in range(r):
                        words[start + j] += ' '
                    res.append((' ' * q).join(words[start:i]))
                start = i
                wordLen = 0
            wordLen += len(w)
        # 最後一行
        last = ' '.join(words[start:])
        res.append(last + ' ' * (maxWidth - len(last)))
        return res

複雜度

• 時間：O(N)，N 為總字符數。
• 空間：O(N) 輸出。