68. Text Justification

Input : words = ["This","is","an","example","of","text","justification."], maxWidth = 16
Output:
[
  "This    is    an",   // 8 letters + 8 extra spaces split over 2 gaps → 4 + 4
  "example  of text",   // 13 letters + 3 extra spaces over 2 gaps → 2 + 1 (left gap gets the extra)
  "justification.  "    // last line: left-justified, trailing spaces
]

// 演算法：兩階段 / Two-phase algorithm.
// 1) 用雙指標貪心地把單字分組到每一行 / Two-pointer greedy grouping per line.
// 2) 對每一行依「最後一行 / 單字行 / 一般行」三種情況排版 / Format each line by case.
// 時間 O(總字元數), 空間 O(輸出大小) / Time O(total chars), space O(output size).

#include <stdlib.h>   // malloc, free / 動態記憶體
#include <string.h>   // strlen, memcpy / 字串長度與位元組複製

char** fullJustify(char** words, int wordsSize, int maxWidth, int* returnSize) {
    // 最多每個單字一行，所以行數上限 = wordsSize / At most one word per line, so cap = wordsSize.
    char** result = (char**)malloc(sizeof(char*) * wordsSize);
    int lineCount = 0;            // 已產生的行數 / number of lines produced so far
    int i = 0;                    // 這一行的第一個單字 index / first word index of current line

    while (i < wordsSize) {
        // ---- 階段 1：決定這一行放哪些單字 / Pick words that fit on this line ----
        int j = i;                // j 會掃到第一個放不下的單字 / j scans to the first word that won't fit
        int lineLen = 0;          // 只計算字母長度，不含空格 / letter length only, no spaces yet
        // 條件：放完 words[j] 後仍需 (j - i) 個分隔空格 / after taking words[j] we still need (j-i) separators
        while (j < wordsSize &&
               lineLen + (int)strlen(words[j]) + (j - i) <= maxWidth) {
            lineLen += (int)strlen(words[j]);  // 累加字母長度 / accumulate letter count
            j++;                               // 嘗試下一個單字 / try next word
        }
        // 此時 words[i..j-1] 是這行的單字 / words[i..j-1] are the chosen words

        int wordCount   = j - i;                  // 這行有幾個單字 / how many words on this line
        int totalSpaces = maxWidth - lineLen;     // 還需要塞入幾個空格 / total spaces to place

        // ---- 階段 2：把這行字串建出來 / Build the line string ----
        // 配置 maxWidth + 1 個 byte（多 1 個放 ''）/ allocate maxWidth + 1 bytes (one for '')
        char* line = (char*)malloc(maxWidth + 1);
        int pos = 0;                              // line 目前的寫入位置 / current write index in line

        // 最後一行 OR 只有 1 個單字 → 左對齊 / Last line or single-word line → left-justify
        if (j == wordsSize || wordCount == 1) {
            for (int k = i; k < j; k++) {
                int len = (int)strlen(words[k]);
                memcpy(line + pos, words[k], len);    // 複製單字到 line / copy word bytes
                pos += len;                            // 移動寫入指標 / advance write pointer
                if (k < j - 1) {                       // 不是最後一個單字 / not the last word
                    line[pos++] = ' ';                 // 單空格分隔 / single space separator
                }
            }
            while (pos < maxWidth) line[pos++] = ' '; // 行尾補空格 / pad trailing spaces
        } else {
            // 一般行：平均分配空格 / Regular line: distribute spaces evenly
            int gaps       = wordCount - 1;            // 空隙數 / number of gaps
            int baseSpaces = totalSpaces / gaps;       // 每隙的基本空格 / base spaces per gap
            int extra      = totalSpaces % gaps;       // 餘下的空格從左邊先發 / leftover spaces, leftmost first

            for (int k = i; k < j; k++) {
                int len = (int)strlen(words[k]);
                memcpy(line + pos, words[k], len);     // 寫入單字 / write the word
                pos += len;
                if (k < j - 1) {                       // 不是最後一個就要放空格 / not last → add gap
                    // 前 extra 個空隙多放 1 個空格 / first `extra` gaps get one extra space
                    int spaces = baseSpaces + ((k - i) < extra ? 1 : 0);
                    for (int s = 0; s < spaces; s++) line[pos++] = ' ';
                }
            }
        }
        line[maxWidth] = '';        // C 字串結尾 / null-terminate the C string
        result[lineCount++] = line;   // 收進結果陣列 / store the line in the result array
        i = j;                        // 下一行從 j 開始 / next line begins at j
    }

    *returnSize = lineCount;          // 透過輸出參數回傳行數 / report total lines back via out-param
    return result;                    // 回傳指向所有行的指標陣列 / return the array of line pointers
}

// 演算法同 C 版：貪心分組 + 三種情況排版 / Same algorithm as C: greedy grouping + 3-case formatting.
// 用 std::string 自動管理記憶體，append(n, ch) 直接重複空格 / std::string handles memory; append(n,ch) repeats a char.

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> result;          // 最終輸出 / final output lines
        int n = (int)words.size();      // 單字總數 / total word count
        int i = 0;                      // 當前行的第一個單字 / first word index of the current line

        while (i < n) {
            // ---- 階段 1：找出能放入這行的單字範圍 [i, j) / Find the word range that fits ----
            int j = i;                  // j 會停在第一個放不下的單字 / j stops at the first word that won't fit
            int lineLen = 0;            // 字母總長（不含空格）/ letter-only length so far
            while (j < n &&
                   lineLen + (int)words[j].size() + (j - i) <= maxWidth) {
                lineLen += (int)words[j].size();   // 加上這個單字的字母數 / add letter count
                ++j;                               // 試下一個單字 / try next
            }

            int wordCount   = j - i;                // 這行單字數量 / number of words this line
            int totalSpaces = maxWidth - lineLen;   // 剩餘要填入的空格 / spaces left to fill

            // ---- 階段 2：根據情況組裝這行 / Build the line by case ----
            string line;
            line.reserve(maxWidth);                 // 預先保留容量避免重新配置 / reserve to avoid reallocs

            if (j == n || wordCount == 1) {
                // 最後一行或單字行 → 左對齊 / Last line or single-word line → left-justify
                for (int k = i; k < j; ++k) {
                    line += words[k];               // 串接單字 / append the word
                    if (k < j - 1) line += ' ';     // 單空格分隔 / single space between words
                }
                line.append(maxWidth - line.size(), ' '); // 右側補空格 / pad the right side
            } else {
                // 一般行：平均分配 / Regular line: distribute spaces evenly
                int gaps       = wordCount - 1;      // 空隙數 / gap count
                int baseSpaces = totalSpaces / gaps; // 每隙基本空格 / base per gap
                int extra      = totalSpaces % gaps; // 左側多分的空格數 / extras going to left gaps

                for (int k = i; k < j; ++k) {
                    line += words[k];                // 接上單字 / append word
                    if (k < j - 1) {                 // 不是最後一個單字 / not the last word on this line
                        int spaces = baseSpaces + ((k - i) < extra ? 1 : 0); // 前 extra 個 gap +1 / first `extra` gaps get +1
                        line.append(spaces, ' ');    // 一次塞 spaces 個空格 / push that many spaces at once
                    }
                }
            }
            result.push_back(std::move(line));       // move 進結果，省一次複製 / move into result to avoid copy
            i = j;                                   // 下一行從 j 開始 / next line begins at j
        }
        return result;                               // 回傳全部行 / return all lines
    }
};