3 min read leetcode

68. Text Justification

68. Text Justification
Photo by Markus Spiske / Unsplash

68. Text Justification

題意

給定一個字串陣列 words，代表每個單字（字串中沒有任何空白），以及一個整數 maxWidth，代表每一行的最大長度。請模擬文字編輯器的自動換行功能，將單字排列成多行文字，滿足以下要求：

  • 每行應該放入盡可能多的單字，但總長度不可超過 maxWidth。
  • 單字之間至少要有一個空格。
  • 單字之間的空格應該盡可能平均分配，若無法平均分配，則左側的空格數應該比右側多。
  • 若一行只能放入一個單字，則該行的其餘部分用空格填充。
  • 對於最後一行，單字之間只需用一個空格連接，並在行尾填充空格至 maxWidth。

限制

  • 1 <= words.length <= 300
  • 1 <= words[i].length <= 20
  • words[i] 只包含英文字母和符號。
  • 1 <= maxWidth <= 100
  • words[i].length <= maxWidth

思路

  • 行內單字選擇：我們需要在每行盡可能多地放入單字，但不能超過 maxWidth。
    • 判斷條件為：已放入的單字總長度 wordsLength，加上單字之間的空格數 spaces = wordsCount - 1，再加上下一個單字的長度，不能超過 maxWidth。
      • 若滿足，則繼續將下一個單字加入當前行。
      • 若不滿足，則將當前行的單字進行排版，開始新的一行。
  • 空格分配：
    • 定義：
      • wordsCount：當前行的單字數。
      • wordsLength：當前行所有單字的總長度。
      • spaces：需要分配的總空格數，計算方式為 maxWidth - wordsLength。
      • slots：單字間的間隙數，計算方式為 wordsCount - 1。
    • 一般情況（非最後一行且 wordsCount > 1）：
      • 每個間隙的最小空格數為 spaces / slots。
      • 多餘的空格數為 spaces % slots，從左側開始依次分配一個額外的空格。
    • 特殊情況：
      • 若當前行只有一個單字，則該單字後面填充空格至 maxWidth。
      • 最後一行的單字之間只需用一個空格連接，行尾填充空格至 maxWidth。

實作

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;
    }
};

時間與空間複雜度分析

  • 時間複雜度：O(N)，其中 N 是 words 的總單字數。
    • 分析：我們只需遍歷一次 words 陣列。在每次迭代中，內部的 while 迴圈最多也只會遍歷剩餘的單字。因此，總的時間複雜度為線性。
  • 空間複雜度：O(N)，用於存儲結果 ans。
    • 分析：我們需要額外的空間來存儲排版後的每一行。結果的總長度與輸入的單字總數及 maxWidth 有關，但不會超過 O(N)。

Justin