AC Python code beats 96%


  • 0
    H

    The 'left' and 'right' space seems to be a big trap -_-

    class Solution(object):
        def fullJustify(self, words, maxWidth):
            """
            :type words: List[str]
            :type maxWidth: int
            :rtype: List[str]
            """
            n = len(words)
            if maxWidth == 0:   return ['']
            res = []
            i, j, cur_w = 0, 0, 0
            while j < n:
                if cur_w == 0:  # the first str, add no space
                    cur_w += len(words[j])
                    j += 1
                elif cur_w+1+len(words[j]) <= maxWidth: # later strs, add at least one space for each word
                    cur_w += 1+len(words[j])
                    j += 1
                else:
                    # arrange the row containing words[i:j] (not include words[j])
                    cur_w -= (j-i-1)    # cur_w includes each one space between words, so we subtract them
                    space = maxWidth-cur_w  # total spaces  
                    if j-i-1 == 0:
                        right, left = 0, 0
                    else:
                        num_left = space%(j-i-1)    # number of left-kind spaces (each one has one more space than right-kind)
                        right, left = space//(j-i-1), space//(j-i-1)+1  # length of each right-kind or lef-kind space
                    s = ''
                    for k in xrange(i, j):
                        if k == i:  
                            s += words[k]
                        elif k <= i+num_left:  
                            s += ' '*left + words[k]
                            cur_w += left
                        else:  
                            s += ' '*right + words[k]
                            cur_w += right 
                    s += ' '*(maxWidth-cur_w)   # in case this row has only 1 str
                    res.append(s)
                    cur_w, i = 0, j # move forward
            # arrange the last row
            s, cur_w = '', 0
            for k in xrange(i, j):
                if k == i:  
                    s += words[k] 
                    cur_w += len(words[k])
                else:   
                    s += ' ' + words[k] 
                    cur_w += len(words[k]) + 1
            s += ' '*(maxWidth-cur_w)
            res.append(s)
            return res
    

Log in to reply
 

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