根据题干描述的贪心算法,对于每一行,我们首先确定最多的是可以放置多少单词,这样可以得到该行的空格个数,从而确定该行单词之间的空格个数。
根据题目中填充空格的细节,我们分以下三种情况讨论:
- 当前行是最后一行:单词左对齐,且单词之间应只有一个空格,在行末填充剩余空格;
- 当前行不是最后一行,且只有一个单词;该单词左对齐,在行末填充空格;
- 当前行不是最后一行,且不只有一个单词;设当前单词数为numWords,空格数为numSpaces,我们需要将空格均匀分配在单词之间,则单词之间应至少由avgSpaces = 个空格,对于多出来的extraSpaces=numSpaces mod (numWords - 1)个空格,应填在前extraSpaces个单词之间。因此,前extraSpaces个单词之间填充avgSpaces+1个空格,其余单词之间填充avgSpaces个空格。