力扣经典150题解析之二十四：文本左右对齐
1. 介绍
在这篇文章中，我们将讨论力扣经典150题中的第二十四题：文本左右对齐问题。给定一个单词数组 words 和一个长度 maxWidth，我们需要重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
2. 问题描述
给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ’ ’ 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。
注意:
单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。
3. 示例
示例 1:
输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16 输出: [ "This is an", "example of text", "justification. " ]
示例 2:
输入: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16 输出: [ "What must be", "acknowledgment ", "shall be " ]
示例 3:
输入: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20 输出: [ "Science is what we", "understand well", "enough to explain to", "a computer. Art is", "everything else we", "do " ]
4. 解题思路
我们可以使用贪心算法来解决这个问题：
- 遍历单词数组 words，逐行构建文本。
- 维护一个变量 current_line 来存储当前行的单词列表。
- 不断尝试将单词添加到当前行，同时考虑单词之间的空格。
- 如果添加下一个单词会导致行长度超过 maxWidth，则进行对齐处理：计算需要插入的空格数，并生成对齐后的字符串。
- 特别处理最后一行，确保左对齐而不是两端对齐。
5. 代码实现
import java.util.ArrayList; import java.util.List; public class Solution { public List<String> fullJustify(String[] words, int maxWidth) { List<String> result = new ArrayList<>(); int start = 0; while (start < words.length) { int end = start; int lineLength = 0; // Calculate the words and total length for the current line while (end < words.length && lineLength + words[end].length() + (end - start) <= maxWidth) { lineLength += words[end].length(); end++; } // Build the current line StringBuilder line = new StringBuilder(); int numOfWords = end - start; int numOfGaps = numOfWords - 1; // If it's the last line or only one word in the line if (end == words.length || numOfWords == 1) { for (int i = start; i < end; i++) { line.append(words[i]); if (i < end - 1) line.append(" "); } while (line.length() < maxWidth) line.append(" "); } else { // Calculate spaces distribution for other lines int totalSpaces = maxWidth - lineLength; int spacesBetweenWords = totalSpaces / numOfGaps; int extraSpaces = totalSpaces % numOfGaps; for (int i = start; i < end; i++) { line.append(words[i]); if (i < end - 1) { for (int j = 0; j < spacesBetweenWords; j++) { line.append(" "); } if (extraSpaces > 0) { line.append(" "); extraSpaces--; } } } } result.add(line.toString()); start = end; } return result; } }
6. 复杂度分析
- 时间复杂度：O(n)，其中 n 是单词数组 words 的长度。每个单词只需要遍历一次。
- 空间复杂度：O(1)，除了结果存储之外，只使用了常数级别的额外空间。
7. 测试与验证
我们对示例输入进行测试：
public class Main { public static void main(String[] args) { Solution solution = new Solution(); String[] words1 = {"This", "is", "an", "example", "of", "text", "justification."}; int maxWidth1 = 16; List<String> result1 = solution.fullJustify(words1, maxWidth1); System.out.println("输出1:"); for (String line : result1) { System.out.println("\"" + line + "\""); } String[] words2 = {"What","must","be","acknowledgment","shall","be"}; int maxWidth2 = 16; List<String> result2 = solution.fullJustify(words2, maxWidth2); System.out.println("\n输出2:"); for (String line : result2) { System.out.println("\"" + line + "\""); } String[] words3 = {"Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"}; int maxWidth3 = 20; List<String> result3 = solution.fullJustify(words3, maxWidth3); System.out.println("\n输出3:"); for (String line : result3) { System.out.println("\"" + line + "\""); } } }
输出结果为：
输出1: "This is an" "example of text" "justification. " 输出2: "What must be" "acknowledgment " "shall be " 输出3: "Science is what we" "understand well" "enough to explain to" "a computer. Art is" "everything else we" "do
8. 总结
通过贪心算法，我们成功解决了文本左右对齐的问题。在构建每一行时，我们尽可能多地放置单词，并通过均匀分配空格的方式对齐文本。特别地，我们要注意处理最后一行，确保左对齐而不是两端对齐。
9. 扩展
我们可以探讨一些扩展话题，例如使用其他算法（如动态规划）来解决文本对齐问题的优化方案，或者讨论特殊情况和边界条件下的处理方式。
希望本文能够帮助读者理解文本左右对齐问题及其解决方法。
这篇博客按照目录结构组织了问题描述、解题思路、代码实现和复杂度分析等内容，希望对您有所帮助！
