给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。
注意:
单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。
示例 1:
输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
输出:
[
"This is an",
"example of text",
"justification. "
]
代码
class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> ans; //储存答案
string str; //临时的一个string的variable
vector<int> index; //用于我们添加 " " 的vector，这个储存每个进去的word在str里的index
for(int i = 0; i < words.size(); ++i)
{
//当加上这个单词小于maxWidth时我们可以加上这个word，然后将此时word在str里的index
//储存进index vector， 然后注意我们要添加一个" "为下一个word做准备
if(str.size() + words[i].size() < maxWidth)
{
str += words[i];
index.push_back(str.size());
str += ' ';
}
//当长度正好时我们就可以直接加上这个word然后push进ans
//注意我们要将str 还有 index vector还原，因为我们要到下一行了
else if(str.size() + words[i].size() == maxWidth)
{
str += words[i];
ans.push_back(str);
str = "";
index.clear();
}
//这个else说明此时的str加上这个word[i]已经超过了maxWidth(此时还没有加上word[i]))
else
{
//先计算出我们需要多少个额外的" "。
int space = maxWidth - str.size();
//如果只有一个word在str里说明我们什么也不用做
//反之如果有一个以上的话我们就需要先将word[i-1]添加的" "给erase
//因为此时word[i-1]会变成最后的字符，所以我们不需要给word[i-1]添加" "
//所以我们将他的index移除， 然后需要加上额外的被erase的那个" "
if(index.size() > 1)
{
str.erase(index.back(), 1);
index.pop_back();
space++;
}
//开始计算平均每个字符间需要多少个" "
//x代表平均的" "，剩下没分配完的 " "给到y,然后给前面的y个word额外加1个" "
int x = 0, y = 0;
if(!index.empty())
{
x = space/index.size();
y = space%index.size();
}
for (int j = index.size()-1; j >= 0; j--)
str.insert(index[j], string(x + (j < y ? 1 : 0), ' '));
ans.push_back(str);
//还原
str = "";
index.clear();
//注意这里我们没有加上word[i]所以我们要将i decrement重新讨论
--i;
}
}
//最后一行扫尾
if(!str.empty())
{
if(str.size() < maxWidth)
str += string(maxWidth - str.size(), ' ');
ans.push_back(str);
}
return ans;
}
};