Leetcode: 68. Text Justification

Problem Statement

Patterns

Prompts

Solution

The solution consists on simulating the rules that are describes in the problem statement. Pack as much words possible while distributing them evenly. The trick part becomes how to implement it in a clear and concise way. All that we need are two values to decide when to flush or extend a line: number of words and total number of chars to be flushed. If these values, we can determine if the line exceeded the max length and compute the number of spaces required when flushing the line. Time complexity and space are \(O(n)\). 

from typing import List


class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        letters_on_line, line = 0, []
        ans = []
        for word in words:
            if letters_on_line + len(line) + len(word) > maxWidth:
                b = len(line) - 1 if len(line) > 1 else 1
                l = maxWidth - letters_on_line
                s, r = l // b, l % b
                cur = ""
                for lword in line:
                    if cur:
                        cur += " " * (s + int(r > 0))
                        r -= 1
                    cur += lword
                ans.append(cur + " " * (maxWidth - len(cur)))
                letters_on_line, line = 0, []
            letters_on_line += len(word)
            line.append(word)
        if line:
            ans.append(
                " ".join(line) + " " * (maxWidth - letters_on_line - (len(line) - 1))
            )
        return ans


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