LeetCode Text Justification

LeetCode解題之Text Justification

原題

把一個集合的單詞按照每行L個字符存放，不足的在單詞間添加空格，每行要兩端對齊(即兩端都要是單詞)，如果空格不能均勻分布在所有間隔中，那麼左邊的空格要多於右邊的空格，最後一行靠左對齊，每個單詞間一個空格。

注意點：

例子：

輸入: words = [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”], maxWidth = 16

輸出:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

解題思路

這道題比較繁瑣，題目就一大段。采用雙指針的方法來標記當前行的單詞，如果加上下一個單詞的長度和每個單詞間至少一個空格時的總長度大於目標長度，說明此時的單詞就是該行應該存放的。要分是否只有一個單詞還是多個單詞進行討論，如果有多個單詞，需要平均分配單詞間的空格。現在可以知道總的空格數和單詞間隔數，所以計算單詞間的間隔比較簡單，注意多余的空格要優先添加到左邊的單詞間隔中。不要忘記添加最後一行的單詞。

AC源碼

class Solution(object):
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        start = end = 0
        result, curr_words_length = [], 0
        for i, word in enumerate(words):
            if len(word) + curr_words_length + end - start  > maxWidth:
                if end - start == 1:
                    result.append(words[start] + ' ' * (maxWidth - curr_words_length))
                else:
                    total_space = maxWidth - curr_words_length
                    space, extra = divmod(total_space, end - start - 1)
                    for j in range(extra):
                        words[start + j] += ' '
                    result.append((' ' * space).join(words[start:end]))
                curr_words_length = 0
                start = end = i
            end += 1
            curr_words_length += len(word)
        result.append(' '.join(words[start:end]) + ' ' * (maxWidth - curr_words_length - (end - start - 1)))
        return result


if __name__ == "__main__":
    assert Solution().fullJustify(["This", "is", "an", "example", "of", "text", "justification."], 16) == [
        "This    is    an",
        "example  of text",
        "justification.  "
    ]