每天一道LeetCode-----将单词数组分成多行，每行长度相同，单词之间用空格分隔，要求空格尽量均匀分布

Text Justification

原题链接Text Justification

将以这个字符串数组重组成几行，每个字符串用空格分隔，要求

• 每行的长度相同
• 每行的空格需要均匀分配，且每个单词之间至少有一个空格
• 最后一行尽量将空格放在最后面

首先思路是记录已遍历到的单词的总长度，判断是否还能容纳当前遍历到的这个单词。

• 如果能，即之前总长度加上这个单词长度以及一个分隔空格没有超过规定长度，继续遍历下一个
• 如果不能，那么就将之前遍历到的所有单词组成一行，改行需要满足上面三个约束

可以用两个下标指针记录当前遍历到的单词，[front, back)表示这个范围的单词可以组成一行，而加上back后则不能。

难点在计算每个单词之间空格的数量，均匀分布空格的意思是

• 假设保证每块空格长度相同的前提下还剩余n个空格，那么就将前n块空格的每个空格长度加一

[front, back)表示这个范围有back - front - 1个单词，len记录这个范围的长度（注，这个长度计算了一个空格在里面，即每个单词之间至少有一个空格，这个空格长度计算在len中了）
那么每个单词之间均匀的空格数应该是(maxWidth - len) / (back - front - 1) + 1
+1表示将len中记录的用于分隔的单词加上

但是，对于最后一行，因为要保证空格尽量在后面，其实就是保证每个单词之间只能有一个空格。
所以计算单词之间空格数量的方法为

int spaces = 1; if(back != words.size() && back != front + 1) {spaces = (maxWidth - len) / (back - front - 1) + 1; }

如果back == front + 1，说明这一行只有一个单词，那么分隔为1即可

除了每个单词均匀的空格数之外，如果剩余n个空格，那么需要将前n个空格块每一个都增加一个空格。计算这个n的方法其实就是计算剩余多少个空格

int spaces = 1; int extra = 0; if(back != words.size() && back != front + 1) {spaces = (maxWidth - len) / (back - front - 1) + 1;extra = (maxWidth - len) % (back - front - 1); }

找到了每个空格块的数量，就可以组成一行的字符串了。不过要注意前extra个空格快的空格数量是spaces + 1
先处理一行中前extra个空格块

res.emplace_back(words[front++]); while(extra--) {res.back().append(spaces+1, ' ');res.back().append(words[front++]); }

再处理该行剩下的空格块

while(front < back) {res.back().append(spaces, ' ');res.back().append(words[front++]); }

此时，这一行字符的总数量已经是maxWidth了，但是考虑到最后一行的情况，上述的space是1而extra为0，追加一遍之后总数量不是maxWidth，因为要将空格尽量放在后面，所以这里需要将剩余的空格追加上

res.back().append((maxWidth - res.back().size()), ' ');

完整代码如下

class Solution { public:vector<string> fullJustify(vector<string>& words, int maxWidth) {vector<string> res;int back = 0;while(back < words.size()){int front = back;int len = words[back++].size();while(back < words.size() && len + 1 + words[back].size() <= maxWidth){len += 1 + words[back].size();++back;}int spaces = 1;int extra = 0;if(back != words.size() && back != front + 1){spaces = (maxWidth - len) / (back - front - 1) + 1;extra = (maxWidth - len) % (back - front - 1);}res.emplace_back(words[front++]);while(extra--){res.back().append(spaces+1, ' ');res.back().append(words[front++]);}while(front < back){res.back().append(spaces, ' ');res.back().append(words[front++]);}res.back().append((maxWidth - res.back().size()), ' ');}return res;} };

本题主要难点在确定空格数，逻辑上用while比for循环清晰不少

总结

以上是生活随笔为你收集整理的每天一道LeetCode-----将单词数组分成多行，每行长度相同，单词之间用空格分隔，要求空格尽量均匀分布的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。