python - 分析以下代码的时间和空间复杂度

问题描述

来自leetcode的问题：

https://leetcode.com/problems/text-justification/description/

给定一个单词数组和一个宽度 maxWidth，对文本进行格式化，使每一行都恰好有 maxWidth 字符并且完全（左和右）对齐。

你应该用贪婪的方式包装你的话；也就是说，在每一行中包含尽可能多的单词。必要时填充额外的空格 ' ' ，以便每行都有 maxWidth 字符。

单词之间的额外空格应尽可能均匀分布。如果一行上的空格数在单词之间分布不均，则左侧的空槽将比右侧的槽分配更多的空格。

对于文本的最后一行，它应该是左对齐的，并且在单词之间没有插入额外的空格。

原始代码：

   class Solution:
        def fullJustify(self, words, maxWidth):
            ans, curr, word_length = [], [], 0
            words.append(' ' * maxWidth)
            for w in words:
                if word_length + len(w) + len(curr) > maxWidth:
                    space = maxWidth-word_length 
                    if w != words[-1]:
                        for i in range(space):
                            curr[i%(len(curr)-1 or 1)] += ' '
                        ans.append(''.join(curr))
                    else:
                        ans.append(' '.join(curr) + ' ' * (space - (len(curr) - 1)))
                    curr = []
                    word_length = 0
                curr += [w]
                word_length += len(w)            

            return ans

所以有2个for循环，一个在另一个里面。第二个 for 循环由每次更改但始终小于“maxWidth”的空间确定。第一个循环的时间复杂度为 O(n)，整体时间复杂度是多少？

标签： pythonpython-3.xtime-complexity

python - 分析以下代码的时间和空间复杂度

问题描述

解决方案

推荐阅读