LeetCode 68: Text Justification (Greedy Line Packing + Space Distribution)
LeetCode 68StringGreedyToday we solve LeetCode 68 - Text Justification.
Source: https://leetcode.com/problems/text-justification/
English
Problem Summary
Given an array of words and a target width maxWidth, output fully justified lines. Each line (except the last) must have exactly maxWidth characters, with spaces distributed as evenly as possible and extra spaces assigned to the left slots first.
Key Insight
Use greedy line packing: put as many words as possible into the current line. Once the line range is fixed, formatting is deterministic: either left-justify (last line or single-word line) or fully justify (split spaces across gaps).
Brute Force and Limitations
A brute approach tries many break points and checks formatting validity, but line breaks are actually forced by the maximum width. Greedy packing is sufficient and much simpler.
Optimal Algorithm Steps (Greedy + Formatter)
1) Start at index i, greedily expand j while the line still fits.
2) Compute total word characters in [i, j).
3) If this is last line or only one word, left-justify and pad trailing spaces.
4) Otherwise, compute spaces = maxWidth - wordsLen, gaps = (j - i - 1).
5) Put spaces / gaps base spaces in each gap, and give first spaces % gaps gaps one extra space.
Complexity Analysis
Time: O(totalCharacters) (each word processed once, each line built once).
Space: O(1) extra besides output.
Common Pitfalls
- Forgetting that the last line must be left-justified.
- Not handling the single-word line as a special case.
- Distributing extra spaces to the right instead of the left.
- Missing final trailing padding to exact maxWidth.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> ans = new ArrayList<>();
int n = words.length;
for (int i = 0; i < n; ) {
int j = i;
int wordsLen = 0;
while (j < n && wordsLen + words[j].length() + (j - i) <= maxWidth) {
wordsLen += words[j].length();
j++;
}
int gaps = j - i - 1;
StringBuilder sb = new StringBuilder();
if (j == n || gaps == 0) {
for (int k = i; k < j; k++) {
if (k > i) sb.append(' ');
sb.append(words[k]);
}
while (sb.length() < maxWidth) sb.append(' ');
} else {
int totalSpaces = maxWidth - wordsLen;
int base = totalSpaces / gaps;
int extra = totalSpaces % gaps;
for (int k = i; k < j; k++) {
sb.append(words[k]);
if (k < j - 1) {
int count = base + ((k - i) < extra ? 1 : 0);
for (int s = 0; s < count; s++) sb.append(' ');
}
}
}
ans.add(sb.toString());
i = j;
}
return ans;
}
}func fullJustify(words []string, maxWidth int) []string {
ans := make([]string, 0)
n := len(words)
for i := 0; i < n; {
j := i
wordsLen := 0
for j < n && wordsLen+len(words[j])+(j-i) <= maxWidth {
wordsLen += len(words[j])
j++
}
gaps := j - i - 1
var b strings.Builder
if j == n || gaps == 0 {
for k := i; k < j; k++ {
if k > i {
b.WriteByte(' ')
}
b.WriteString(words[k])
}
for b.Len() < maxWidth {
b.WriteByte(' ')
}
} else {
totalSpaces := maxWidth - wordsLen
base := totalSpaces / gaps
extra := totalSpaces % gaps
for k := i; k < j; k++ {
b.WriteString(words[k])
if k < j-1 {
cnt := base
if (k - i) < extra {
cnt++
}
for s := 0; s < cnt; s++ {
b.WriteByte(' ')
}
}
}
}
ans = append(ans, b.String())
i = j
}
return ans
}class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> ans;
int n = (int)words.size();
for (int i = 0; i < n; ) {
int j = i, wordsLen = 0;
while (j < n && wordsLen + (int)words[j].size() + (j - i) <= maxWidth) {
wordsLen += (int)words[j].size();
++j;
}
int gaps = j - i - 1;
string line;
if (j == n || gaps == 0) {
for (int k = i; k < j; ++k) {
if (k > i) line.push_back(' ');
line += words[k];
}
line.append(maxWidth - (int)line.size(), ' ');
} else {
int totalSpaces = maxWidth - wordsLen;
int base = totalSpaces / gaps;
int extra = totalSpaces % gaps;
for (int k = i; k < j; ++k) {
line += words[k];
if (k < j - 1) {
int cnt = base + ((k - i) < extra ? 1 : 0);
line.append(cnt, ' ');
}
}
}
ans.push_back(move(line));
i = j;
}
return ans;
}
};class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
ans = []
n = len(words)
i = 0
while i < n:
j = i
words_len = 0
while j < n and words_len + len(words[j]) + (j - i) <= maxWidth:
words_len += len(words[j])
j += 1
gaps = j - i - 1
if j == n or gaps == 0:
line = ' '.join(words[i:j])
line += ' ' * (maxWidth - len(line))
else:
total_spaces = maxWidth - words_len
base = total_spaces // gaps
extra = total_spaces % gaps
parts = []
for k in range(i, j):
parts.append(words[k])
if k < j - 1:
cnt = base + (1 if (k - i) < extra else 0)
parts.append(' ' * cnt)
line = ''.join(parts)
ans.append(line)
i = j
return ans/**
* @param {string[]} words
* @param {number} maxWidth
* @return {string[]}
*/
var fullJustify = function(words, maxWidth) {
const ans = [];
const n = words.length;
for (let i = 0; i < n; ) {
let j = i;
let wordsLen = 0;
while (j < n && wordsLen + words[j].length + (j - i) <= maxWidth) {
wordsLen += words[j].length;
j++;
}
const gaps = j - i - 1;
let line = '';
if (j === n || gaps === 0) {
line = words.slice(i, j).join(' ');
line += ' '.repeat(maxWidth - line.length);
} else {
const totalSpaces = maxWidth - wordsLen;
const base = Math.floor(totalSpaces / gaps);
const extra = totalSpaces % gaps;
for (let k = i; k < j; k++) {
line += words[k];
if (k < j - 1) {
const cnt = base + ((k - i) < extra ? 1 : 0);
line += ' '.repeat(cnt);
}
}
}
ans.push(line);
i = j;
}
return ans;
};中文
题目概述
给定单词数组和目标宽度 maxWidth，你需要把文本排版成“左右对齐”行。除最后一行外，每行长度必须等于 maxWidth，并且空格尽量均匀分配，多出来的空格从左侧间隙开始分配。
核心思路
先贪心装行：当前行尽可能放更多单词。行范围确定后，格式化规则是确定的：最后一行或单词数为 1 时左对齐；其余情况执行完全对齐并分配空格。
基线解法与不足
可以尝试枚举行切分点再验证，但这会引入不必要复杂度。因为每一行在 maxWidth 约束下其实是“能放多少就放多少”，贪心即可得到正确分行。
最优算法步骤（贪心装行 + 格式化）
1）从 i 出发，贪心扩展到最大 j，满足行仍可放下。
2）统计 [i, j) 单词总字符数。
3）若是最后一行或只有一个单词：单词间一个空格，末尾补空格。
4）否则计算 spaces = maxWidth - wordsLen 与 gaps = j - i - 1。
5）每个间隙放 spaces / gaps 个空格，前 spaces % gaps 个间隙再多放一个空格。
复杂度分析
时间复杂度：O(总字符数)。
空间复杂度：除输出外为 O(1)。
常见陷阱
- 忘记“最后一行必须左对齐”。
- 单词数为 1 的行没有间隙，必须单独处理。
- 多余空格分配方向写反，应该优先左侧。
- 没有补齐行尾空格，导致长度不足 maxWidth。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> ans = new ArrayList<>();
int n = words.length;
for (int i = 0; i < n; ) {
int j = i;
int wordsLen = 0;
while (j < n && wordsLen + words[j].length() + (j - i) <= maxWidth) {
wordsLen += words[j].length();
j++;
}
int gaps = j - i - 1;
StringBuilder sb = new StringBuilder();
if (j == n || gaps == 0) {
for (int k = i; k < j; k++) {
if (k > i) sb.append(' ');
sb.append(words[k]);
}
while (sb.length() < maxWidth) sb.append(' ');
} else {
int totalSpaces = maxWidth - wordsLen;
int base = totalSpaces / gaps;
int extra = totalSpaces % gaps;
for (int k = i; k < j; k++) {
sb.append(words[k]);
if (k < j - 1) {
int count = base + ((k - i) < extra ? 1 : 0);
for (int s = 0; s < count; s++) sb.append(' ');
}
}
}
ans.add(sb.toString());
i = j;
}
return ans;
}
}func fullJustify(words []string, maxWidth int) []string {
ans := make([]string, 0)
n := len(words)
for i := 0; i < n; {
j := i
wordsLen := 0
for j < n && wordsLen+len(words[j])+(j-i) <= maxWidth {
wordsLen += len(words[j])
j++
}
gaps := j - i - 1
var b strings.Builder
if j == n || gaps == 0 {
for k := i; k < j; k++ {
if k > i {
b.WriteByte(' ')
}
b.WriteString(words[k])
}
for b.Len() < maxWidth {
b.WriteByte(' ')
}
} else {
totalSpaces := maxWidth - wordsLen
base := totalSpaces / gaps
extra := totalSpaces % gaps
for k := i; k < j; k++ {
b.WriteString(words[k])
if k < j-1 {
cnt := base
if (k - i) < extra {
cnt++
}
for s := 0; s < cnt; s++ {
b.WriteByte(' ')
}
}
}
}
ans = append(ans, b.String())
i = j
}
return ans
}class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> ans;
int n = (int)words.size();
for (int i = 0; i < n; ) {
int j = i, wordsLen = 0;
while (j < n && wordsLen + (int)words[j].size() + (j - i) <= maxWidth) {
wordsLen += (int)words[j].size();
++j;
}
int gaps = j - i - 1;
string line;
if (j == n || gaps == 0) {
for (int k = i; k < j; ++k) {
if (k > i) line.push_back(' ');
line += words[k];
}
line.append(maxWidth - (int)line.size(), ' ');
} else {
int totalSpaces = maxWidth - wordsLen;
int base = totalSpaces / gaps;
int extra = totalSpaces % gaps;
for (int k = i; k < j; ++k) {
line += words[k];
if (k < j - 1) {
int cnt = base + ((k - i) < extra ? 1 : 0);
line.append(cnt, ' ');
}
}
}
ans.push_back(move(line));
i = j;
}
return ans;
}
};class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
ans = []
n = len(words)
i = 0
while i < n:
j = i
words_len = 0
while j < n and words_len + len(words[j]) + (j - i) <= maxWidth:
words_len += len(words[j])
j += 1
gaps = j - i - 1
if j == n or gaps == 0:
line = ' '.join(words[i:j])
line += ' ' * (maxWidth - len(line))
else:
total_spaces = maxWidth - words_len
base = total_spaces // gaps
extra = total_spaces % gaps
parts = []
for k in range(i, j):
parts.append(words[k])
if k < j - 1:
cnt = base + (1 if (k - i) < extra else 0)
parts.append(' ' * cnt)
line = ''.join(parts)
ans.append(line)
i = j
return ans/**
* @param {string[]} words
* @param {number} maxWidth
* @return {string[]}
*/
var fullJustify = function(words, maxWidth) {
const ans = [];
const n = words.length;
for (let i = 0; i < n; ) {
let j = i;
let wordsLen = 0;
while (j < n && wordsLen + words[j].length + (j - i) <= maxWidth) {
wordsLen += words[j].length;
j++;
}
const gaps = j - i - 1;
let line = '';
if (j === n || gaps === 0) {
line = words.slice(i, j).join(' ');
line += ' '.repeat(maxWidth - line.length);
} else {
const totalSpaces = maxWidth - wordsLen;
const base = Math.floor(totalSpaces / gaps);
const extra = totalSpaces % gaps;
for (let k = i; k < j; k++) {
line += words[k];
if (k < j - 1) {
const cnt = base + ((k - i) < extra ? 1 : 0);
line += ' '.repeat(cnt);
}
}
}
ans.push(line);
i = j;
}
return ans;
};
Comments