subject

Given an array of words and a length maxWidth, rearrange the words into text with exactly maxWidth characters per line and aligned left and right ends.
You should use "greedy algorithm" to place a given word; That is, put as many words in each line as possible. If necessary, it can be filled with space '' so that each line has exactly maxWidth characters.
It is required to distribute the number of spaces between words as evenly as possible. If the spaces between words in a line cannot be evenly distributed, the number of spaces placed on the left is more than the number of spaces on the right.
The last line of text should be left justified and no additional spaces should be inserted between words.

explain:
A word is a sequence of characters consisting of non whitespace characters.
The length of each word is greater than 0 and less than or equal to maxWidth.
The input word array words contains at least one word.

Example

Input:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
Output:
[
"This is an",
"example of text",
"justification. "
]

Input:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
Output:
[
"What must be",
"acknowledgment ",
"shall be "
]
Explanation: note that the format of the last line should be "shall be" instead of "shall be",
Because the last row should be left aligned, not left and right aligned.
The second line is also left justified because it contains only one word.

Input:
words = ["Science","is","what","we","understand","well","enough","to","explain",
"to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
Output:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]

Source: LeetCode
Link: https://leetcode-cn.com/problems/text-justification
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.

idea

It is divided into two major directions:
1. Extract the words in each line.

Control the judgment condition of each line: while (varsum < = maxwidth + 1 and I < len (words)):
Varsum < = maxwidth + 1: because every time you judge the length, a space is added when you add a word.
For example, in extreme cases: ["enough", "to", "explain", "to"], one line cannot exceed 20. The total word length is 17, with 3 spaces added, which is 20; but the total judgment length is 21.

2. Export by line and place spaces.

Additional spaces can be regarded as added on the basis of equally divided spaces.
Equally divided spaces: total spaces / (number - 1)
Additional spaces are% of the total number of spaces (number - 1), and the rule: the additional spaces must be less than (number - 1)
Therefore, the number of spaces:
First add the necessary spaces. Add additional from the beginning. Add 1 at a time. After adding, the number of additional spaces is - 1

There is only one word in one line and the special cases in the last line should be discussed separately.

realization

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        i,varsum,long,var=0,0,0,0
        varl,res,longl,out,rowout=list(),list(),list(),list(),str()

        #Extract words from each line
        while(i<len(words)):
            varsum=len(words[i])+1
            while(varsum<=maxWidth+1 and i<len(words)):
                varl.append(words[i])
                long+=len(words[i])
                if i+1<len(words):
                    i+=1
                    varsum+=len(words[i])+1
                else:
                    i+=1
            res.append(varl)
            longl.append(long)
            long=0
            varl=[]

        #Place spaces
        for i in range(len(res)):
            sc=maxWidth-longl[i]
            if len(res[i])==1: #1 word situation
                rowout+=str(res[i][0])
                for k in range(sc):
                    rowout+=" "
            elif i==len(res)-1: #Last line
                for q in range(len(res[i])):
                    if q != len(res[i]) - 1:
                        rowout+=str(res[i][q])
                        rowout+=" "
                        sc-=1
                    else:
                        rowout+=str(res[i][q])
                for p in range(sc):
                    rowout+=" "
            else:
                ix = sc/(len(res[i])-1)
                iy=sc%(len(res[i])-1)
                for j in range(len(res[i])):
                    if j != len(res[i]) - 1:
                        rowout += str(res[i][j])
                        for m in range(int(ix)):#The number of equally divided spaces is added first
                            rowout+=" "
                        if iy != 0:
                            rowout+=" "
                            iy-=1
                    else:
                        rowout+=str(res[i][j])
            out.append(rowout)
            rowout=""
        return(out)