텍스트 자리맞추기

문자열 배열words과 너비maxWidth가 주어지면 각 줄에 정확히 maxWidth개의 문자가 있고 완전히(왼쪽 및 오른쪽) 정렬되도록 텍스트 서식을 지정합니다.

탐욕스러운 접근 방식으로 단어를 포장해야 합니다. 즉, 각 줄에 가능한 한 많은 단어를 넣습니다. 필요한 경우 추가 공백' '을 채워 각 줄에 정확히 maxWidth 문자가 포함되도록 합니다.

단어 사이의 여분의 공백은 가능한 한 고르게 분포되어야 합니다. 줄의 공백 수가 단어 간에 균등하게 나뉘지 않으면 왼쪽의 빈 슬롯에 오른쪽의 슬롯보다 더 많은 공간이 할당됩니다.

텍스트의 마지막 줄은 왼쪽 정렬되어야 하며 단어 사이에 추가 공백이 삽입되지 않습니다.

메모:

단어는 공백이 아닌 문자로만 구성된 문자 시퀀스로 정의됩니다.

각 단어의 길이는 0보다 크고 maxWidth를 초과하지 않도록 보장됩니다.

입력 배열words에 하나 이상의 단어가 포함되어 있습니다.

예 1:

입력: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
산출:
[
"이것은 입니다 ",
"텍스트의 예",
"정당화. "
]

예 2:

입력: words = ["What","must","be","acknowledgement","shall","be"], maxWidth = 16
산출:
[
"반드시 되어야 하는 것",
"확인 ",
"한다 "
]
설명: 마지막 줄은 완전히 정렬되는 대신 왼쪽 정렬되어야 하므로 "shall be"대신 "shall be "입니다.
두 번째 줄도 단어가 하나만 포함되어 있기 때문에 왼쪽 정렬됩니다.

예 3:

입력: words = ["과학","이다","무엇","우리","이해하다","잘","충분히","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20
산출:
[
"과학은 우리가 하는 것입니다",
"잘 이해 잘",
"설명하기에 충분하다",
"컴퓨터. 예술은",
"다른 모든 것은 우리",
"하다 "
]

제약:

1 <= words.length <= 300

1 <= words[i].length <= 20

words[i]는 영문자와 기호로만 구성되어 있습니다.

1 <= maxWidth <= 100

words[i].length <= maxWidth

해결책:

class Solution:
    def format(self, words, a, b, maxWidth, p, isLast):
        n = b - a
        if n == 1 or isLast:
            used = p[b] - p[a] + n - 1
            return " ".join(words[a:b]) + " " * (maxWidth - used)
        spaces = maxWidth - (p[b] - p[a])
        gap = spaces // (n - 1)
        k = spaces % (n - 1)
        res = []
        for i in range(a, b):
            res.append(words[i])
            if i == b - 1:
                break
            if k > 0:
                res.append(" " * (gap + 1))
                k -= 1
            else:
                res.append(" " * gap)
        return "".join(res)

    def justify(self, words, maxWidth, p, i, n):
        if i >= n:
            return []
        j = i
        l = 0
        while j < n and l + len(words[j]) <= maxWidth:
            l += len(words[j]) + 1
            j += 1
        rem = self.justify(words, maxWidth, p, j, n)
        return [self.format(words, i, j, maxWidth, p, len(rem) == 0)] + rem

    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        p = [0]
        for w in words:
            p.append(p[-1] + len(w))
        return self.justify(words, maxWidth, p, 0, len(words))