Justify Text

题目描述

解题方法

解法还是比较直接的，但是要把题目的条件问清楚，各种corner case搞清楚！！！

Solution

class Solution:
    # @param A : list of strings
    # @param B : integer
    # @return a list of strings
    def fullJustify(self, A, B):
        result = []
        if not A:
            return []
        if not B:
            return
        length = len(A)
        cur_line_length = 0
        cur_line_word = 0
        start_idx = 0
        idx = 0
        while idx < length:
            if cur_line_length + len(A[idx]) + cur_line_word <= B:
                cur_line_length += len(A[idx])
                cur_line_word += 1
                idx += 1
            else:
                new_line = self.generate(A, B, start_idx, idx-1)
                result.append(new_line)
                cur_line_length = 0
                cur_line_word = 0
                start_idx = idx
        new_line = self.generateLastline(A, B, start_idx, length-1)
        result.append(new_line)

        return result

    def generate(self, A, B, start, end):
        word_length = 0
        word_num = end - start + 1
        newline = ""
        for i in range(start, end+1):
            word_length += len(A[i])
        space_length = B - word_length
        if word_num == 1: # corner case!!!
            newline = A[start] + " " * space_length 
        else:
            avg_space = space_length / (word_num-1)
            remaining_space = space_length % (word_num-1)
            for i in range(start, end+1):
                if i - start < remaining_space:
                    newline += A[i]
                    newline += " " * (avg_space+1)
                elif i == end:
                    newline += A[i]
                else:
                    newline += A[i]
                    newline += " " * avg_space
        return newline

    def generateLastline(self, A, B, start, end):
        newline = ""
        for i in range(start, end+1):
            if i != end:
                newline += A[i] + " "
            else:
                newline += A[i]

        num_space = B - len(newline)
        newline += " " * num_space
        return newline

Reference