68. Text Justification

題意

給一個字串陣列 words 代表每個單字 (字串中沒有任何空白)，並且給定一個 maxWidth 代表每一行的長度，模擬文字編輯器的換行

• 每行字要放盡可能多的單字，單字中間至少有一個空格，但長度不可超過 maxWidth

• 每個字之間的空格要平均分配，若不夠分至少左邊的空格要多於右邊

• 若只夠放一個字，後面就全部填空白

限制

• 1 <= words.length <= 300

• 1 <= words[i].length <= 20

• words[i] consists of only English letters and symbols.

• 1 <= maxWidth <= 100

• words[i].length <= maxWidth

思考題目

• 盡可能在 maxWidth 塞下盡可能多的單字，再根據單字數及總長計算空白後組成字串

  • 已放入的單字總長 + 單字數(空格占用的字數，單字數 - 1) + 目前的單字長 <= maxWidth

    • 是，則繼續填入下一個單字

    • 否，則將目前單字組成一行推入答案，並從當前單字(尚未被放入)開始組成下一行

  • 設每個單字之間的空間稱為 slot，slotCount為其總數，wordsCount為單字數，wordsLength 為所有單字的總長

    • slotCount = wordsCount - 1

    • 第 i個 slot 的長度會是 (maxWidth - wordsLength) / slotCount + ((maxWidth - wordsLength) % slotCount < i ? 1 : 0)

    • 由此可組成長度為 maxWidth 的一行

    • 若 wordsCount == 1，則可用 words[0] + string(maxWidth - words[0].size(), ‘ ‘) 組成一行

• 處理到最後一行的時候，將所有單字用一個空格join起來並補上右側的空白便得到最終答案

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        const int n = words.size();
        vector<string> ans;

        int begin = 0;
        int count = 0;
        for (int i = 0; i < n; i += 1) {
            if (count + (i - begin) + words[i].size() > maxWidth) {
                if (i - begin == 1) {
                    ans.push_back(words[begin] + string(maxWidth - words[begin].size(), ' '));
                } else {
                    int space = maxWidth - count;
                    int eachSpace = space / (i - begin - 1);
                    int remainSpace = space % (i - begin - 1);

                    string line = words[begin];
                    for (int j = begin + 1; j < i; j += 1) {
                        line += string(eachSpace + (remainSpace > 0 ? 1 : 0), ' ');
                        remainSpace -= 1;
                        line += words[j];
                    }
                    ans.push_back(line);
                }
                begin = i;
                count = 0;
            }
            count += words[i].size();
        }

        string line = words[begin];
        for (int i = begin + 1; i < n; i += 1) {
            line += " " + words[i];
        }
        line += string(maxWidth - line.size(), ' ');
        ans.push_back(line);

        return ans;
    }
};