Solution by sha256pki


  • 0
    S

    The straight forward approach is to process each word, pack it in a line as much as possible and once the packing of word would lead to overflowing given "maxWidth", then put a line in paragraph after distributing spaces.

    Required variables -

            paragraph = []   # stores final answer, collection of lines
            line   = []  # collection of words, at any point line will never exceed maxWidth
            length = 0 # number of nonspace characters (a running sum of all words in line)
            i      = 0 # an auxiliary counter variable to iterate over given list of words
    

    A problem thus can be decomposed in two following major sub-problems

    1. packing a "line" with words as much as possible - By "as much as possible", number of non space characters + space characters must fit within "maxWidth". Number of non space character is sum of length of words and number of space characters is one less than number of words as at least one space should be between two words).
      In other words "word" must go in "line" as long as adding a word doesn't cause "line" to exceed "maxWidth". "length" is running sum of length of words and "line" variable is collection of words.

    If a new word could be added in a line then -

    1. Number of non-space characters = length + len(word)
    2. Number of words that would get one space = len(line) (before word is added in line)

    Following python code handles this -

            while i < len(words):
                if length + len(line) + len(words[i]) <= maxWidth:
                    line   += words[i],
                    length += len(words[i])
                    i += 1
    
    1. Distributing spaces - Once line can no longer accept new words without going beyond "maxWidth", a line must be transferred into paragraph. But before that each line must be processed to distribute space. This is further divided into two subproblems
      2.1 Handling of every line except last line
      2.1.1 a line has more than one words
      For this type of line, Problem states following -
      "Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right."

    In simple words it means to distributed spaces in a round-robin fashion.

    Find out how many spaces must go inside a line and treating 'line' as circular array, give one space each to every word in a line as long as it is possible. Following code handles this

                    totalSpaces = maxWidth - length
                    j = 0
                    if len(line) > 1:
                        while totalSpaces:
                            line[j] += ' '
                            totalSpaces -= 1
                            j += 1
                            j %= ( len(line) -1 )
    
    

    2.1.2 A line has one word
    Now look at "corner cases" description -
    "A line other than the last line might contain only one word. What should you do in this case? In this case, that line should be left-justified."
    What it means is the only word in the line receives all the spaces. Following code handles this -

                        line[0] += ' '*totalSpaces
    

    2.2 Handling of last line
    Problem description states -
    " For the last line of text, it should be left justified and no extra space is inserted between words. "
    What it means is - each word except the last - receives one space each. The last word receives rest of the remaining spaces. Following code handles this -

                totalSpaces = maxWidth - length
                if len(line) > 1:
                    for j in range(len(line) - 1):
                        line[j] += ' '
                        totalSpaces -= 1
                line[-1] += ' '*totalSpaces
                paragraph += ''.join(line),
    

    Combining solution of above sub problems, the final solution will look like below -

    class Solution(object):
        def fullJustify(self, words, maxWidth):
            """
            :type words: List[str]
            :type maxWidth: int
            :rtype: List[str]
            """
            paragraph = []
            line   = []
            length = 0
            i      = 0
            while i < len(words):
                if length + len(line) + len(words[i]) <= maxWidth:
                    line   += words[i],
                    length += len(words[i])
                    i += 1
                else:
                    totalSpaces = maxWidth - length
                    j = 0
                    if len(line) > 1:
                        while totalSpaces:
                            line[j] += ' '
                            totalSpaces -= 1
                            j += 1
                            j %= ( len(line) -1 )
                    else:
                        line[0] += ' '*totalSpaces
                    paragraph += ''.join(line),
                    line = []
                    length = 0
    
            if line:
                totalSpaces = maxWidth - length
                if len(line) > 1:
                    for j in range(len(line) - 1):
                        line[j] += ' '
                        totalSpaces -= 1
                line[-1] += ' '*totalSpaces
                paragraph += ''.join(line),
    
            return paragraph
    

    Complexity analysis - If there're "n" total words, "w" is length of each word, and each line can have at most "k" spaces. Then outer most loop runs for "n" iterations. Space distribution loop runs for "k" iterations, and in each iteration, performs string append operation over increasing length -
    w + w + 1 + w + 2 + ..... + w + k = w x ( 1 + 2 + 3 .... + k+1) = w x (k+1) x (k+2) // 2

    So it could be argued that the complexity is O ( n x w x k^2)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.