68. Text Justification

Hard

Description

給定單字陣列 words 和最大寬度 maxWidth，格式化文字使每行恰好 maxWidth 個字元，使用「完全對齊」（左右對齊）。盡可能多放單字，左邊的空格間距不少於右邊，最後一行左對齊。

Example:

Input: words = [“This”,“is”,“an”,“example”,“of”,“text”,“justification.”], maxWidth = 16 Output: [“This is an”, “example of text”, “justification. “]

Intuition#

核心思路：Greedy 打包——盡可能在每行塞入最多單字，然後根據剩餘空格均勻分配。最後一行特殊處理（左對齊）。

第一步：決定每行放哪些單字（Greedy，盡量多放）
第二步：計算空格分配。若一行有 k 個間隔和 extraSpaces 個空格，每個間隔至少 extraSpaces/k 個，前 extraSpaces%k 個間隔多一個
特殊情況：只有一個單字的行和最後一行都是左對齊

Approaches#

1: Line-by-Line Simulation#

概念: 逐行打包單字，計算空格分配
時間複雜度: O(n * maxWidth) - n 為單字數，每行構建字串 O(maxWidth)
空間複雜度: O(maxWidth) - 每行字串

class Solution {
    fun fullJustify(words: Array<String>, maxWidth: Int): List<String> {
        val result = mutableListOf<String>()
        var i = 0

        while (i < words.size) {
            // 決定這行放哪些單字
            var lineLen = words[i].length
            var j = i + 1
            while (j < words.size && lineLen + 1 + words[j].length <= maxWidth) {
                lineLen += 1 + words[j].length
                j++
            }

            val wordsInLine = j - i
            val totalSpaces = maxWidth - (lineLen - (wordsInLine - 1))  // 總空格數

            val sb = StringBuilder()

            if (wordsInLine == 1 || j == words.size) {
                // 單字行或最後一行：左對齊
                for (k in i until j) {
                    if (k > i) sb.append(' ')
                    sb.append(words[k])
                }
                while (sb.length < maxWidth) sb.append(' ')
            } else {
                val gaps = wordsInLine - 1
                val spacePerGap = totalSpaces / gaps
                val extraGaps = totalSpaces % gaps

                for (k in i until j) {
                    sb.append(words[k])
                    if (k < j - 1) {
                        val spaces = spacePerGap + if (k - i < extraGaps) 1 else 0
                        repeat(spaces) { sb.append(' ') }
                    }
                }
            }

            result.add(sb.toString())
            i = j
        }

        return result
    }
}

⭐2: Clean Simulation with Helper#

概念: 抽取 helper 函數使邏輯更清晰，分離「打包」和「格式化」的職責
時間複雜度: O(n * maxWidth) - 同上
空間複雜度: O(maxWidth) - 每行字串

class Solution {
    fun fullJustify(words: Array<String>, maxWidth: Int): List<String> {
        val result = mutableListOf<String>()
        var i = 0

        while (i < words.size) {
            // Greedy: 盡量多放單字
            var j = i
            var curLen = 0
            while (j < words.size && curLen + words[j].length + (j - i) <= maxWidth) {
                curLen += words[j].length
                j++
            }

            val line = buildLine(words, i, j, curLen, maxWidth, j == words.size)
            result.add(line)
            i = j
        }

        return result
    }

    private fun buildLine(
        words: Array<String>, start: Int, end: Int,
        wordsLen: Int, maxWidth: Int, isLastLine: Boolean
    ): String {
        val sb = StringBuilder()
        val gaps = end - start - 1
        val totalSpaces = maxWidth - wordsLen

        if (gaps == 0 || isLastLine) {
            // 左對齊
            for (k in start until end) {
                if (k > start) sb.append(' ')
                sb.append(words[k])
            }
            while (sb.length < maxWidth) sb.append(' ')
        } else {
            val spacePerGap = totalSpaces / gaps
            val extra = totalSpaces % gaps

            for (k in start until end) {
                sb.append(words[k])
                if (k < end - 1) {
                    repeat(spacePerGap + if (k - start < extra) 1 else 0) {
                        sb.append(' ')
                    }
                }
            }
        }

        return sb.toString()
    }
}

空格分配的關鍵：totalSpaces / gaps 是每個間隔的基本空格數，totalSpaces % gaps 是需要多加一個空格的間隔數。多餘的空格從左到右分配（前 extra 個間隔各多一個空格）。

🔑 Takeaways#

Pattern: 文字格式化 -> Greedy 打包 + 模擬空格分配
關鍵技巧: 整除和取餘用於均勻分配（totalSpaces / gaps 和 totalSpaces % gaps）；分離打包與格式化邏輯使程式碼更清晰。這題主要考驗程式碼實作能力而非演算法