問題描述

給定一個單詞數組?words?和一個長度?maxWidth?，重新排版單詞，使其成為每行恰好有?maxWidth?個字符，且左右兩端對齊的文本。

你應該使用 “貪心算法” 來放置給定的單詞；也就是說，盡可能多地往每行中放置單詞。必要時可用空格?' '?填充，使得每行恰好有?maxWidth?個字符。

要求盡可能均勻分配單詞間的空格數量。如果某一行單詞間的空格不能均勻分配，則左側放置的空格數要多于右側的空格數。

文本的最后一行應為左對齊，且單詞之間不插入額外的空格。

注意:

• 單詞是指由非空格字符組成的字符序列。
• 每個單詞的長度大于 0，小于等于?maxWidth。
• 輸入單詞數組?words?至少包含一個單詞。

解題思路

步驟一：行的構建

首先，我們需要確定每行可以包含哪些單詞。從當前索引開始，盡可能多地添加單詞到當前行，直到添加下一個單詞會使行長度超過 maxWidth。這個過程中，我們需要計算已包括的單詞總長度加上必要的最小空格數（每兩個單詞之間至少一個空格）。

步驟二：計算空格

一旦確定了可以放在同一行的單詞，接下來需要計算這些單詞之間應分配多少空格：

• 非最后一行： 若行中有多于一個單詞，需要將可用空格數（maxWidth 減去當前行單詞字符總數）均勻分配到單詞間隙中。如果空格數不能被均勻分配，多出的空格應從左到右依次分配。
• 最后一行： 單詞之間只放一個空格，行尾用空格填充至 maxWidth。

步驟三：構建字符串

根據計算出的空格數構建每一行的字符串。對于非最后一行，每兩個單詞之間添加計算出的空格數。對于最后一行，單詞之間添加一個空格，然后在行末添加足夠的空格以達到 maxWidth。

代碼實現

class Solution {
public:vector<string> fullJustify(vector<string>& words, int maxWidth) {vector<string> result;int n = words.size();int index = 0;while (index < n) {// 確定當前行可以包含的單詞數量。int lineLength = words[index].size();int last = index + 1;while (last < n &&lineLength + words[last].size() + 1 <= maxWidth) {lineLength += words[last].size() + 1; // +1 是因為單詞之間的空格last++;}// 構建當前行。string line = words[index];int numWordsInLine = last - index;// 如果是最后一行或者行中只有一個單詞。if (last == n || numWordsInLine == 1) {for (int i = index + 1; i < last; i++) {line += " " + words[i];}line += string(maxWidth - line.length(),' '); // 填充行尾空格以滿足最大寬度} else {// 不是最后一行并且行中有多個單詞。int totalSpaces =maxWidth - (lineLength -(numWordsInLine -1)); // 減去在 lineLength 計算中已經計數的空格int spacesBetweenWords = totalSpaces / (numWordsInLine - 1);int extraSpaces = totalSpaces % (numWordsInLine - 1);for (int i = index + 1; i < last; i++) {int spacesToApply =spacesBetweenWords + (i - index <= extraSpaces ? 1 : 0);line += string(spacesToApply, ' ') + words[i];}}result.push_back(line);index = last;}return result;}
};