[数据结构与算法]LeetCode-【模拟】文本左右对齐

题目描述

测试用例

题目分析

1. 最后一行与前几行不一样：前几行空格均匀分配；最后一行空格一个单词最多后面紧接着一个空格
2. 可遍历一遍整个words，记录子串的左右边界单词，遍历到当前单词时分三种情况：加入当前单词后，子串尚未充满；子串刚好充满；子串过长
3. 如果子串尚未充满，则更新右边界
4. 如果子串刚好充满，构建当前完整子串
5. 如果子串过长，构建当前完整子串，并把当前单词加入下一个子串
6. “构建子串”这个子函数，只需要把空格均分，从左往右多余的每两个单词之间最多加一个，额外空格用完为止
7. “构建最后子串”这个子函数，左对齐安排单词和最多一个空格，用完单词后，长度不够，空格来凑！

python实现

class Solution(object):
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        left,right = 0,0    #当前子串左右边界单词
        len_of_list = 0     #当前子串已用长度（含空格）
        ans = []
        for index in range(len(words)):
            if len_of_list == 0:
                left,right = index,index
            if len_of_list + len(words[index]) < maxWidth:
                #当前子串还有剩余长度
                len_of_list += len(words[index]) + 1
                right = index   #及时更新右边界
            elif len_of_list + len(words[index]) == maxWidth:
                #刚好无额外空格
                len_of_list += len(words[index])
                right = index
                #构建子串
                substr = self.construct_substr(words, left, right, maxWidth)
                len_of_list = 0
                #放入最终结果
                ans.append(substr)

            else:   #过长则处理之前字串，并存下当前单词
                #构建子串
                substr = self.construct_substr(words, left, right, maxWidth)
                len_of_list = 0
                #放入最终结果
                ans.append(substr)

                left,right = index,index
                len_of_list += min(len(words[index]) + 1, maxWidth) #防止当前单词长度等于 maxWidth


        
        if len_of_list != 0:
            #如果仍剩余单词
            laststr = self.construct_laststr(words, left, right, maxWidth)
            ans.append(laststr)
        

        return ans

    
    def construct_substr(self, words, left, right, maxWidth):
        #构建子串
        '''
        rtype:str
        包含：words[left]~words[right]以及若干均匀分布空格
        '''
        substr = ''
        num_of_words = right - left + 1     #单词数量
        if num_of_words == 1:
            substr += words[left]
            while len(substr)<maxWidth:
                substr += ' '
            return substr

        len_of_words = 0        #纯单词长度
        for i in range(left, right+1):
            len_of_words += len(words[i])
        average_space = (maxWidth - len_of_words)/(num_of_words-1)     #平均分配的空格数
        extra_space = (maxWidth - len_of_words) % (num_of_words-1)     #额外空格数
                                                                       #每两个单词间分配一个
        for i in range(left, right+1):
            word = words[i]
            substr += word
            if i != right:
                substr += ' '*average_space
                if extra_space != 0:
                    substr += ' '
                    extra_space -= 1
        
        #断言
        assert len(substr)==maxWidth, '构建字串长度不正确'
        return substr

    def construct_laststr(self, words, left, right, maxWidth):
        #处理最后一个字串
        '''
        rtype:str
        包含：words[left]~words[right]以及若干单空格
        '''
        laststr = ''
        for i in range(left, right+1):
            word = words[i]
            laststr += word
            if i != right:
                laststr += ' '
        
        while len(laststr) < maxWidth:
            #长度不够，空格来凑
            laststr += ' '
        
        return laststr

代码性能