1.该题主要考察字符串操作。
2.主要思路是，如果单词为当前行的第一个单词，则不需要考虑插入空格，如果单词为当前行的第二个单词，则需要补充空格。这样可以尽可能多地添加单词到同一行中。
3.当完成单词的选择后，需要进行空格补充，从第二个单词开始遍历（第一个单词前面不需要补充空格），每次在单词前面补充一个空格，知道满足宽度要求。
4.在3中，条件是从第二个单词开始补充。需要注意的是，假如一个单词为一行，但是这行不是结束行，那么在这个单词后面补充足够多的空格即可。
Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactlyL characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.
Return the formatted lines as:
[ "This is an", "example of text", "justification. " ]
Note: Each word is guaranteed not to exceed L in length.
- A line other than the last line might contain only one word. What should you do in this case?
In this case, that line should be left-justified.
AC代码：
[c language=”++”]
class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
int newStrCount = 0;
int n = words.size();
int nowIdx = 0;
vector<string> result(0);
while (nowIdx < n)
{
int nowStrWidth = 0;
int startIdx = nowIdx;
int endIdx = nowIdx;
for (; nowIdx < n; nowIdx++)
{
if (nowStrWidth == 0 && maxWidth >= nowStrWidth + words[nowIdx].size())
{//这是这个字符串的第一个单词,包含了最后一个单词单独为一行的状态
endIdx = nowIdx;
nowStrWidth += words[nowIdx].size();
}
else if (nowStrWidth > 0 && maxWidth >= nowStrWidth + words[nowIdx].size() + 1)
{//不是字符串的第一个单词,需要补充一个空格
endIdx = nowIdx;
nowStrWidth += words[nowIdx].size() + 1;
}
else//大于的话退出循环
break;
}
string thisStr = "";//这次生成的text string
vector<string> thisStrWords(0);
for (int i = startIdx; i <= endIdx; i++)
{
thisStrWords.push_back(words[i]);
}
if (nowIdx == n)//最后一行的单词
{
thisStr += thisStrWords[0];
for (int i = 1; i < thisStrWords.size(); i++)
{//添加单词，从第二个单词开始，每个单词前面都需要补充一个空格
thisStr = thisStr+" "+thisStrWords[i];
}
for (int i = 0; i < maxWidth – nowStrWidth; i++)
thisStr += " ";//补充缺少的空格
}
else
{
for (int i = 1; i < thisStrWords.size(); i++)
{//因为之前对压进来的单词没有加空格，现在先加上
thisStrWords[i] = " " + thisStrWords[i];
}
//开始进行justification
while (nowStrWidth < maxWidth)
{
if (thisStrWords.size() > 1)
{//如果有两个单词或以上
for (int i = 1; i < thisStrWords.size(); i++)
{//在第二个单词前面补充空格，优先补充左边的空格，一旦符合要求，马上退出
if (nowStrWidth == maxWidth)//满足宽度要求
break;
thisStrWords[i] = " " + thisStrWords[i];
nowStrWidth++;
}
}
else
{//如果只有一个单词
int blankCount = maxWidth – nowStrWidth;
for (int i = 0; i < blankCount; i++)
{
nowStrWidth++;
thisStrWords[0] += " ";//补充缺少的空格
}
}
}
for (int i = 0; i < thisStrWords.size(); i++)
{//把单词合并成text string
thisStr += thisStrWords[i];
}
}
result.push_back(thisStr);
}
return result;
}
};
[/c]