給定單字陣列
words和最大寬度maxWidth，格式化文字使每行恰好maxWidth個字元，使用「完全對齊」（左右對齊）。盡可能多放單字，左邊的空格間距不少於右邊，最後一行左對齊。
Example:
Input: words = [“This”,“is”,“an”,“example”,“of”,“text”,“justification.”], maxWidth = 16 Output: [“This is an”, “example of text”, “justification. “]
Intuition
TIP
核心思路：Greedy 打包——盡可能在每行塞入最多單字，然後根據剩餘空格均勻分配。最後一行特殊處理（左對齊）。
- 第一步：決定每行放哪些單字（Greedy，盡量多放）
- 第二步：計算空格分配。若一行有
k個間隔和extraSpaces個空格，每個間隔至少extraSpaces/k個，前extraSpaces%k個間隔多一個 - 特殊情況：只有一個單字的行和最後一行都是左對齊
Approaches
1. Line-by-Line Simulation — O(n * maxWidth) / O(maxWidth)
- Idea: 逐行打包單字，計算空格分配
- Time:
O(n * maxWidth)- n 為單字數，每行構建字串 O(maxWidth) - Space:
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 — O(n * maxWidth) / O(maxWidth)
- Idea: 抽取 helper 函數使邏輯更清晰，分離「打包」和「格式化」的職責
- Time:
O(n * maxWidth)- 同上 - Space:
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()
}
}WARNING
空格分配的關鍵：totalSpaces / gaps 是每個間隔的基本空格數，totalSpaces % gaps 是需要多加一個空格的間隔數。多餘的空格從左到右分配（前 extra 個間隔各多一個空格）。
🔑 Takeaways
- Pattern: 文字格式化 -> Greedy 打包 + 模擬空格分配
- Key trick: 整除和取餘用於均勻分配（
totalSpaces / gaps和totalSpaces % gaps）；分離打包與格式化邏輯使程式碼更清晰。這題主要考驗程式碼實作能力而非演算法