题目链接：Text Justification

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 exactly L 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.

Corner Cases:

  • 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.

这道题的要求是给定一组单词和长度L，以两端对齐的方式格式化文本使每行仅仅有L个字符。当中最后一行左对齐。每行的单词间可能须要补充额外的空格。假设空格数目不能整除单词间隔的数目，则左側数目要多于右側。

字符串处理，处理每行文本的时候。分为2步：

  1. 统计并记录每行L个字符最多能够容纳几个单词。这里须要注意一下，统计的是。对于从第二个開始的单词。都有预留一个空格的位置。

  2. 计算单词间的空格数目并填入单词和空格。在不是最后1行的情况下，如果单词间隔有n个。剩余L-l个空位置，这每一个位置须要(L-l)/n个空格。当中前(L-l)%n个间隔各须要多1个空格。

    当然，最后如果没有满L个字符，须要在后面补充空格直到L个字符。

时间复杂度：O(n)

空间复杂度：O(1)

 1 class Solution
 2 {
 3 public:
 4     vector<string> fullJustify(vector<string> &words, int L)
 5     {
 6         vector<string> vs;
 7         // i：当前行的開始单词位置
 8         // j：当前行的最后一个单词的下一位置
 9         // l：当前行的全部单词的总长度
10         for(int i = 0, j, l; i < words.size(); i = j)
11         {
12             string s = words[i];
13             // 计算j和l的值
14             for(j = ++ i, l = s.size(); j < words.size() && l + words[j].size() <= L - (j - i + 1); ++ j)
15                 l += words[j].size();
16             // 构造当前行字符串
17             for(int k = 0; k < j - i; ++ k)
18             {
19                 if(j < words.size()) // 假设不是最后一行，平均分配单词间的空格
20                     s += string((L - l) / (j - i) + ((L - l) % (j - i) > k), ' ');
21                 else // 假设是最后一行。这单词间补充1个空格
22                     s += ' ';
23                 s += words[i + k];
24             }
25             // 补充空格到指定长度
26             s += string(L - s.size(), ' ');
27             vs.push_back(s);
28         }
29         return vs;
30     }
31 };