15 lines Python solution with comments


  • 0
    Z

    1.divide the words

    2.use a function adjust the spacing

    3.special deal with the last line

    def fullJustify(self, words, maxWidth):
        l, r, numWords, res = 0, 0, len(words), []
        while l < numWords:
            L = len(words[l])
            while r+1 < numWords and L + len(words[r+1]) + 1 <= maxWidth: # greedy find range
                r += 1
                L = L + len(words[r]) + 1
            if r != numWords-1:     # regular cases, use helper function
                res.append(self.just(words[l:r+1], maxWidth-L))
            else:                   # the last line
                res.append(" ".join(words[l:r+1]) + " " * (maxWidth-L))
            l = r = r+1
        return res
        
    def just(self, words, added):
        if added == 0:      # if no added space, join words and return
            return " ".join(words)
        dens = len(words) - 1
        if dens == 0:       # if just one word, all space added to end
            return words[0] + " " * added
        gaps = [" " for _ in range(dens)]
        for i in range(added):
            gaps[i%dens] += " "     # evenly distribute added space
        res = ""
        for i in range(dens):
            res += words[i] + gaps[i]   # combine word and space
        return res + words[-1]  # add last word
    

    Same algorithm and shrink to 15 lines

    def fullJustify(self, words, maxWidth):
        l, r, numWords, res = 0, 0, len(words), []
        while l < numWords:
            L = len(words[l])
            while r+1 < numWords and L + len(words[r+1]) + 1 <= maxWidth: # greedy find range
                L, r= L + len(words[r+1]) + 1, r+1
            # if no need to adjust spacing, output directly
            res += [self.just(words[l:r+1], maxWidth-L)] if r != numWords-1 and r-l > 0 and maxWidth-L > 0 \
                    else [" ".join(words[l:r+1]) + " " * (maxWidth-L)]
            l = r = r+1
        return res
    
    def just(self, words, added):
        gaps = [" " for _ in range(len(words)-1)]
        for i in range(added):
            gaps[i%(len(words)-1)] += " "   # adjust spacing
        return "".join([words[i]+gaps[i] for i in range(len(words)-1)]) + words[-1]

Log in to reply
 

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