Concise and commented Python solution, 36 ms


  • 0
    D
    def fullJustify(self, words, maxWidth):
            ans = []
            while words != []:
                # Keep track of locations of potential spaces
                spaces = []
                line = words.pop(0)
                single_word = True
                
                # Pop words into line until words empties or maxWidth is reached.
                while words != [] and len(line) + 1 + len(words[0]) <= maxWidth:
                    spaces.append(len(line))
                    line += ' ' + words.pop(0)
                    single_word = False
                    
                # Take care of last line and single word line cases.
                if words == [] or single_word:
                    line += ' ' * (maxWidth - len(line))
                    ans.append(line)
                    continue
                
                nspaces = len(spaces)
                needed = maxWidth - len(line)
                
                # Increase number of spaces in between words
                for i in range(nspaces):
                    added = needed / nspaces
                    if needed % nspaces > i:
                        added += 1
                    line = line[:spaces[i]] + ' '*added + line[spaces[i]:]
                    # Shift locations of subsequent spaces
                    for j in range(i+1, nspaces):
                        spaces[j] += added
                ans.append(line)
                
            return ans

  • 0
    D

    words.pop(0) takes too much time. I think it increase the time complexity to O(n^2), where n is the total length of input.


Log in to reply
 

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