1. 问题背景与需求拆解文本对齐是文字处理软件和排版系统中的基础功能LeetCode第68题文本左右对齐要求我们实现一个模拟文本两端对齐的算法。给定一个单词数组words和一个长度maxWidth我们需要重新排版单词使其成为每行恰好有maxWidth个字符且左右两端对齐的文本。这个问题的实际应用场景非常广泛文字处理软件如Word的自动排版功能网页内容的自适应显示终端输出的格式化打印移动端应用的文本渲染问题的核心难点在于如何合理分配单词间的空格使每行恰好填满最后一行需要特殊处理左对齐单行只有一个单词时的对齐方式2. 贪心算法基础与问题适配贪心算法(Greedy Algorithm)是一种在每一步选择中都采取当前状态下最优决策的算法策略。对于文本对齐问题贪心策略体现在行内单词选择尽可能多地在一行中放置单词直到放不下为止空格分配优先均匀分配空格无法均匀时左边比右边多具体实现时需要考虑当前行已放置的单词总长度单词间至少需要一个空格剩余空格的计算与分配贪心算法在此问题中的适用性证明局部最优每行尽可能多放单词减少总行数全局最优最终得到行数最少且符合格式要求的排版3. 实现方案一迭代式贪心分配3.1 基本实现步骤def fullJustify(words, maxWidth): res, cur, num_letters [], [], 0 for word in words: # 检查当前行是否能容纳新单词 if num_letters len(word) len(cur) maxWidth: # 分配空格 for i in range(maxWidth - num_letters): cur[i%(len(cur)-1 or 1)] res.append(.join(cur)) cur, num_letters [], 0 cur.append(word) num_letters len(word) # 处理最后一行 res.append( .join(cur).ljust(maxWidth)) return res3.2 关键点解析行构建逻辑num_letters记录当前行字母总数len(cur)代表当前单词数每个单词间至少一个空格判断条件num_letters len(word) len(cur) maxWidth确保不超限空格分配技巧使用模运算i%(len(cur)-1 or 1)实现循环分配or 1处理单单词情况这种分配方式确保左边空格不少于右边最后一行处理使用 .join(cur)自然拼接ljust(maxWidth)实现左对齐并填充空格3.3 复杂度分析时间复杂度O(N)其中N是所有单词字符总数空间复杂度O(M)存储结果所需空间M为输出行数4. 实现方案二分段处理法4.1 实现代码def fullJustify(words, maxWidth): def justify_line(line, maxWidth, is_lastFalse): if is_last or len(line) 1: return .join(line).ljust(maxWidth) total_spaces maxWidth - sum(len(w) for w in line) space_between, extra divmod(total_spaces, len(line)-1) spaces [ *(space_between (1 if i extra else 0)) for i in range(len(line)-1)] spaces.append() # 最后一个单词不加空格 return .join([ws for w, s in zip(line, spaces)]) res, current_line [], [] current_length 0 for word in words: if current_length len(word) len(current_line) maxWidth: res.append(justify_line(current_line, maxWidth)) current_line, current_length [], 0 current_line.append(word) current_length len(word) res.append(justify_line(current_line, maxWidth, is_lastTrue)) return res4.2 方案对比特性迭代式分配分段处理法代码结构紧凑逻辑集中模块化职责分离空格分配动态计算显式计算特殊行处理需要额外判断通过参数控制可读性较低较高性能略优略低4.3 边界情况处理单单词行必须左对齐右侧填充空格至maxWidth最后一行单词间单空格右侧填充超长单词题目保证单词长度≤maxWidth实际工程中需要预处理5. 工程实践中的优化技巧5.1 性能优化字符串拼接避免频繁字符串相加使用join()代替预计算提前计算单词长度总和减少运行时重复计算内存管理控制中间变量数量重用数据结构5.2 代码可维护性函数拆分将空格分配逻辑独立分离行构建和格式化注释策略解释复杂逻辑标记关键计算点测试用例设计常规情况边界情况单单词、最后一行等极端情况大量短单词6. 算法扩展与变种6.1 其他对齐方式居中对齐两侧空格均匀分配奇数差时右侧多一个右对齐左侧填充空格单词顺序不变分散对齐强制拉伸所有空格即使一行未满也两端对齐6.2 多语言适配中文处理无空格概念按字符而非单词分割混合文本中英文混排规则标点符号处理复杂排版考虑连字符保留原始格式7. 实际应用案例7.1 命令行工具输出# 表格数据对齐打印 data [[Name, Age, Occupation], [John, 28, Engineer], [Alice, 32, Researcher]] col_widths [max(len(row[i]) for row in data) for i in range(len(data[0]))] for row in data: print( .join(word.ljust(width) for word, width in zip(row, col_widths)))7.2 网页文本渲染// CSS实现两端对齐 .justified-text { text-align: justify; text-justify: inter-word; hyphens: auto; }7.3 移动端UI布局// SwiftUI实现自适应文本 Text(Long text to be justified) .multilineTextAlignment(.leading) .frame(maxWidth: .infinity, alignment: .leading)8. 常见问题与调试技巧8.1 典型错误模式空格计算错误忘记基础空格分配不均匀最后一行处理不当错误应用两端对齐空格填充不足索引越界单单词行特殊处理空输入处理8.2 调试方法可视化调试打印中间结果用特殊字符标记空格单元测试def test_justify(): assert fullJustify([This, is, an], 16) [ This is an ] assert fullJustify([What,must,be], 16) [ What must be ]边界测试空输入单单词恰好满行9. 算法选择与进阶思考9.1 贪心算法的适用性虽然贪心算法在此问题中表现良好但需要注意不是所有文本排版问题都适用更复杂的排版需要动态规划考虑可读性时可能需要其他策略9.2 替代方案比较动态规划计算全局最优解处理复杂约束更高时间复杂度回溯法穷尽所有可能适用于小规模输入可找到多种解分治法将文本分段处理适合并行计算合并阶段复杂在实际工程中选择算法时需要权衡时间复杂度要求结果质量需求实现复杂度可维护性对于大多数文本对齐场景贪心算法提供了最佳性价比。
1. 问题背景与需求拆解文本对齐是文字处理软件和排版系统中的基础功能LeetCode第68题文本左右对齐要求我们实现一个模拟文本两端对齐的算法。给定一个单词数组words和一个长度maxWidth我们需要重新排版单词使其成为每行恰好有maxWidth个字符且左右两端对齐的文本。这个问题的实际应用场景非常广泛文字处理软件如Word的自动排版功能网页内容的自适应显示终端输出的格式化打印移动端应用的文本渲染问题的核心难点在于如何合理分配单词间的空格使每行恰好填满最后一行需要特殊处理左对齐单行只有一个单词时的对齐方式2. 贪心算法基础与问题适配贪心算法(Greedy Algorithm)是一种在每一步选择中都采取当前状态下最优决策的算法策略。对于文本对齐问题贪心策略体现在行内单词选择尽可能多地在一行中放置单词直到放不下为止空格分配优先均匀分配空格无法均匀时左边比右边多具体实现时需要考虑当前行已放置的单词总长度单词间至少需要一个空格剩余空格的计算与分配贪心算法在此问题中的适用性证明局部最优每行尽可能多放单词减少总行数全局最优最终得到行数最少且符合格式要求的排版3. 实现方案一迭代式贪心分配3.1 基本实现步骤def fullJustify(words, maxWidth): res, cur, num_letters [], [], 0 for word in words: # 检查当前行是否能容纳新单词 if num_letters len(word) len(cur) maxWidth: # 分配空格 for i in range(maxWidth - num_letters): cur[i%(len(cur)-1 or 1)] res.append(.join(cur)) cur, num_letters [], 0 cur.append(word) num_letters len(word) # 处理最后一行 res.append( .join(cur).ljust(maxWidth)) return res3.2 关键点解析行构建逻辑num_letters记录当前行字母总数len(cur)代表当前单词数每个单词间至少一个空格判断条件num_letters len(word) len(cur) maxWidth确保不超限空格分配技巧使用模运算i%(len(cur)-1 or 1)实现循环分配or 1处理单单词情况这种分配方式确保左边空格不少于右边最后一行处理使用 .join(cur)自然拼接ljust(maxWidth)实现左对齐并填充空格3.3 复杂度分析时间复杂度O(N)其中N是所有单词字符总数空间复杂度O(M)存储结果所需空间M为输出行数4. 实现方案二分段处理法4.1 实现代码def fullJustify(words, maxWidth): def justify_line(line, maxWidth, is_lastFalse): if is_last or len(line) 1: return .join(line).ljust(maxWidth) total_spaces maxWidth - sum(len(w) for w in line) space_between, extra divmod(total_spaces, len(line)-1) spaces [ *(space_between (1 if i extra else 0)) for i in range(len(line)-1)] spaces.append() # 最后一个单词不加空格 return .join([ws for w, s in zip(line, spaces)]) res, current_line [], [] current_length 0 for word in words: if current_length len(word) len(current_line) maxWidth: res.append(justify_line(current_line, maxWidth)) current_line, current_length [], 0 current_line.append(word) current_length len(word) res.append(justify_line(current_line, maxWidth, is_lastTrue)) return res4.2 方案对比特性迭代式分配分段处理法代码结构紧凑逻辑集中模块化职责分离空格分配动态计算显式计算特殊行处理需要额外判断通过参数控制可读性较低较高性能略优略低4.3 边界情况处理单单词行必须左对齐右侧填充空格至maxWidth最后一行单词间单空格右侧填充超长单词题目保证单词长度≤maxWidth实际工程中需要预处理5. 工程实践中的优化技巧5.1 性能优化字符串拼接避免频繁字符串相加使用join()代替预计算提前计算单词长度总和减少运行时重复计算内存管理控制中间变量数量重用数据结构5.2 代码可维护性函数拆分将空格分配逻辑独立分离行构建和格式化注释策略解释复杂逻辑标记关键计算点测试用例设计常规情况边界情况单单词、最后一行等极端情况大量短单词6. 算法扩展与变种6.1 其他对齐方式居中对齐两侧空格均匀分配奇数差时右侧多一个右对齐左侧填充空格单词顺序不变分散对齐强制拉伸所有空格即使一行未满也两端对齐6.2 多语言适配中文处理无空格概念按字符而非单词分割混合文本中英文混排规则标点符号处理复杂排版考虑连字符保留原始格式7. 实际应用案例7.1 命令行工具输出# 表格数据对齐打印 data [[Name, Age, Occupation], [John, 28, Engineer], [Alice, 32, Researcher]] col_widths [max(len(row[i]) for row in data) for i in range(len(data[0]))] for row in data: print( .join(word.ljust(width) for word, width in zip(row, col_widths)))7.2 网页文本渲染// CSS实现两端对齐 .justified-text { text-align: justify; text-justify: inter-word; hyphens: auto; }7.3 移动端UI布局// SwiftUI实现自适应文本 Text(Long text to be justified) .multilineTextAlignment(.leading) .frame(maxWidth: .infinity, alignment: .leading)8. 常见问题与调试技巧8.1 典型错误模式空格计算错误忘记基础空格分配不均匀最后一行处理不当错误应用两端对齐空格填充不足索引越界单单词行特殊处理空输入处理8.2 调试方法可视化调试打印中间结果用特殊字符标记空格单元测试def test_justify(): assert fullJustify([This, is, an], 16) [ This is an ] assert fullJustify([What,must,be], 16) [ What must be ]边界测试空输入单单词恰好满行9. 算法选择与进阶思考9.1 贪心算法的适用性虽然贪心算法在此问题中表现良好但需要注意不是所有文本排版问题都适用更复杂的排版需要动态规划考虑可读性时可能需要其他策略9.2 替代方案比较动态规划计算全局最优解处理复杂约束更高时间复杂度回溯法穷尽所有可能适用于小规模输入可找到多种解分治法将文本分段处理适合并行计算合并阶段复杂在实际工程中选择算法时需要权衡时间复杂度要求结果质量需求实现复杂度可维护性对于大多数文本对齐场景贪心算法提供了最佳性价比。
