Topic describes

Given an array of words and a maxWidth of length, retype the words so that each line has exactly maxWidth characters and is aligned right and left. You should use a "greedy algorithm" to place a given word; That is, put as many words in each line as possible. Use Spaces if necessary' 'Padding so that each line has exactly maxWidth characters. The number of Spaces between words should be distributed as evenly as possible. If the space between words on a line is not evenly distributed, more space is placed on the left than on the right. The last line of text should be left aligned and no extra Spaces inserted between words. Description: Words are sequences of characters that are not Spaces. Each word is longer than0Is less than or equal to maxWidth. The input word array words contains at least one word. Example: Enter: words = ["This"."is"."an"."example"."of"."text"."justification."]
maxWidth = 16Output:"This is an"."example of text"."justification. "] example2: Enter: words = ["What"."must"."be"."acknowledgment"."shall"."be"]
maxWidth = 16Output:"What must be"."acknowledgment "."shall be "Note that the format of the last line should be"shall be "Rather than"shall be"Because the last line should be left aligned, not left and right aligned. The second line is also left justified because it contains only one word. The sample3: Enter: words = ["Science"."is"."what"."we"."understand"."well"."enough"."to"."explain"."to"."a"."computer."."Art"."is"."everything"."else"."we"."do"]
maxWidth = 20Output:"Science is what we"."understand well"."enough to explain to"."a computer. Art is"."everything else we"."do "
]
Copy the code

Answer: Greedy

  1. Use greedy thinking and put as many words on a line as possible
  2. When the line does not fit another word, start a new line. This will tell you what words are in each line
  3. Fill in the blanks according to the words in each line
  4. Let’s do the last row separately

The sample code

def fullJustify(self, words: List[str], maxWidth: int) - >List[str] :
    res, cur, l = [], [], 0
    # Count the words in each line according to greed
    for item in words:
        if l + len(item) <= maxWidth:
            l += (len(item) + 1)
            cur.append(item)
        else:
            res.append(cur)
            l = len(item) + 1
            cur = [item]
    res.append(cur)

    Fill in the blanks according to the words in each line
    ans = []
    for items in res[:-1]:
        count = len(items)
        if count == 1:
            ans.append(items[0] + "" * (maxWidth - len(items[0)))elif count == 2:
            ans.append(items[0] + "" * (maxWidth - len(items[0]) - len(items[1])) + items[1])
        else:
            sumC = sum(len(i) for i in items)
            m = (maxWidth - sumC) // (len(items) - 1)
            n = (maxWidth-sumC) - m*(len(items) - 1)
            a = items[0]
            i = 1
            for w in items[1] :if n > 0:
                    a = a + "" * (m+1) + w
                else:
                    a = a + "" * m + w
                n -= 1

            ans.append(a)

    Handle the last line
    items = res[-1]
    a = items[0]
    for w in items[1:]:
        a += ("" + w)
    a = a + ("" * (maxWidth - len(a)))
    ans.append(a)

    return ans

Copy the code