28-文本左右对齐

给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。 你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。 文本的最后一行应为左对齐，且单词之间不插入额外的空格。 注意: 单词是指由非空格字符组成的字符序列。 每个单词的长度大于 0，小于等于 maxWidth。 输入单词数组 words 至少包含一个单词。 

方法一：基本贪心算法实现

function fullJustify(words: string[], maxWidth: number): string[] {let result: string[] = [];let i = 0;while (i < words.length) {let lineWords: string[] = [];let currentLength = 0;// 尽可能多地往当前行添加单词while (i < words.length && currentLength + words[i].length + lineWords.length <= maxWidth) {lineWords.push(words[i]);currentLength += words[i].length;i++;}let spaces = maxWidth - currentLength;let line = "";if (i === words.length || lineWords.length === 1) {// 最后一行或只有一个单词的行，左对齐line = lineWords.join(" ");line += " ".repeat(maxWidth - line.length);} else {// 非最后一行，均匀分配空格let avgSpaces = Math.floor(spaces / (lineWords.length - 1));let extraSpaces = spaces % (lineWords.length - 1);for (let j = 0; j < lineWords.length - 1; j++) {line += lineWords[j];line += " ".repeat(avgSpaces + (j < extraSpaces? 1 : 0));}line += lineWords[lineWords.length - 1];}result.push(line);}return result;
}// 测试示例
let words = ["This", "is", "an", "example", "of", "text", "justification."];
let maxWidth = 16;
let result = fullJustify(words, maxWidth);
console.log(result);

方法二：拆分逻辑实现

function fullJustify(words: string[], maxWidth: number): string[] {let result: string[] = [];let start = 0;while (start < words.length) {let end = start;let lineLength = 0;// 确定当前行能容纳的单词范围while (end < words.length && lineLength + words[end].length + (end - start) <= maxWidth) {lineLength += words[end].length;end++;}let spaces = maxWidth - lineLength;let line = "";if (end === words.length || end - start === 1) {// 最后一行或只有一个单词的行，左对齐for (let i = start; i < end; i++) {if (i > start) {line += " ";spaces--;}line += words[i];}line += " ".repeat(spaces);} else {// 非最后一行，均匀分配空格let avgSpaces = Math.floor(spaces / (end - start - 1));let extraSpaces = spaces % (end - start - 1);for (let i = start; i < end - 1; i++) {line += words[i];line += " ".repeat(avgSpaces + (i - start < extraSpaces? 1 : 0));}line += words[end - 1];}result.push(line);start = end;}return result;
}// 测试示例
let words2 = ["What", "must", "be", "acknowledgment", "shall", "be"];
let maxWidth2 = 16;
let result2 = fullJustify(words2, maxWidth2);
console.log(result2);

方法三：利用辅助函数实现

function createLine(words: string[], start: number, end: number, maxWidth: number, isLastLine: boolean): string {let lineLength = 0;for (let i = start; i < end; i++) {lineLength += words[i].length;}let spaces = maxWidth - lineLength;let line = "";if (isLastLine || end - start === 1) {// 最后一行或只有一个单词的行，左对齐for (let i = start; i < end; i++) {if (i > start) {line += " ";spaces--;}line += words[i];}line += " ".repeat(spaces);} else {// 非最后一行，均匀分配空格let avgSpaces = Math.floor(spaces / (end - start - 1));let extraSpaces = spaces % (end - start - 1);for (let i = start; i < end - 1; i++) {line += words[i];line += " ".repeat(avgSpaces + (i - start < extraSpaces? 1 : 0));}line += words[end - 1];}return line;
}function fullJustify(words: string[], maxWidth: number): string[] {let result: string[] = [];let start = 0;while (start < words.length) {let end = start;let currentLength = 0;// 确定当前行能容纳的单词范围while (end < words.length && currentLength + words[end].length + (end - start) <= maxWidth) {currentLength += words[end].length;end++;}let isLastLine = end === words.length;let line = createLine(words, start, end, maxWidth, isLastLine);result.push(line);start = end;}return result;
}// 测试示例
let words3 = ["Science", "is", "what", "we", "understand", "well", "enough", "to", "explain", "to", "a", "computer.", "Art", "is", "everything", "else", "we", "do"];
let maxWidth3 = 20;
let result3 = fullJustify(words3, maxWidth3);
console.log(result3);

复杂度分析

• 时间复杂度：三种方法的时间复杂度均为 (O(n))，其中 n 是单词数组 words 中所有字符的总数。因为每个单词只会被处理一次。
• 空间复杂度：三种方法的空间复杂度均为 (O(m))，其中 m 是结果数组的长度，主要用于存储排版后的每行文本。

这些方法的核心思路都是贪心算法，尽可能多地往每行中放置单词，然后根据不同情况（最后一行或非最后一行）来分配空格。不同方法只是在代码结构和实现细节上有所差异。

方法四：动态规划

动态规划的核心在于将大问题拆解为小问题，通过保存子问题的解来避免重复计算。对于这个单词排版问题，我们可以定义状态并找出状态转移方程。

function fullJustify(words: string[], maxWidth: number): string[] {const n = words.length;// cost[i][j] 表示从第 i 个单词到第 j 个单词放在一行的代价const cost: number[][] = new Array(n).fill(0).map(() => new Array(n).fill(Number.MAX_SAFE_INTEGER));// 计算每行放置不同单词组合的代价for (let i = 0; i < n; i++) {let length = 0;for (let j = i; j < n; j++) {if (i === j) {length = words[j].length;} else {length += words[j].length + 1;}if (length <= maxWidth) {cost[i][j] = Math.pow(maxWidth - length, 2);}}}// dp[i] 表示从第 i 个单词开始排版的最小代价const dp: number[] = new Array(n + 1).fill(Number.MAX_SAFE_INTEGER);// 用于记录每个位置的最优分割点const path: number[] = new Array(n + 1).fill(0);dp[n] = 0;// 动态规划计算最小代价和最优分割点for (let i = n - 1; i >= 0; i--) {for (let j = i; j < n; j++) {if (cost[i][j]!== Number.MAX_SAFE_INTEGER) {if (dp[i] > cost[i][j] + dp[j + 1]) {dp[i] = cost[i][j] + dp[j + 1];path[i] = j + 1;}}}}const result: string[] = [];let start = 0;// 根据最优分割点构建排版结果while (start < n) {const end = path[start];const lineWords = words.slice(start, end);let line = "";if (end === n) {// 最后一行左对齐line = lineWords.join(" ");line += " ".repeat(maxWidth - line.length);} else {const spaces = maxWidth - lineWords.reduce((acc, word) => acc + word.length, 0);if (lineWords.length === 1) {line = lineWords[0] + " ".repeat(spaces);} else {const avgSpaces = Math.floor(spaces / (lineWords.length - 1));const extraSpaces = spaces % (lineWords.length - 1);for (let i = 0; i < lineWords.length - 1; i++) {line += lineWords[i];line += " ".repeat(avgSpaces + (i < extraSpaces? 1 : 0));}line += lineWords[lineWords.length - 1];}}result.push(line);start = end;}return result;
}// 测试示例
const words = ["This", "is", "an", "example", "of", "text", "justification."];
const maxWidth = 16;
console.log(fullJustify(words, maxWidth));

方法五：递归回溯

递归回溯是一种通过尝试所有可能的组合来找到最优解的方法。对于这个问题，我们可以递归地尝试将单词放入不同的行，直到找到满足条件的排版方式。

function fullJustify(words: string[], maxWidth: number): string[] {const result: string[] = [];function backtrack(index: number): void {if (index === words.length) {return;}let lineWords: string[] = [];let currentLength = 0;// 尽可能多地往当前行添加单词while (index < words.length && currentLength + words[index].length + lineWords.length <= maxWidth) {lineWords.push(words[index]);currentLength += words[index].length;index++;}let line = "";if (index === words.length) {// 最后一行左对齐line = lineWords.join(" ");line += " ".repeat(maxWidth - line.length);} else {const spaces = maxWidth - currentLength;if (lineWords.length === 1) {line = lineWords[0] + " ".repeat(spaces);} else {const avgSpaces = Math.floor(spaces / (lineWords.length - 1));const extraSpaces = spaces % (lineWords.length - 1);for (let i = 0; i < lineWords.length - 1; i++) {line += lineWords[i];line += " ".repeat(avgSpaces + (i < extraSpaces? 1 : 0));}line += lineWords[lineWords.length - 1];}}result.push(line);backtrack(index);}backtrack(0);return result;
}// 测试示例
const words2 = ["What", "must", "be", "acknowledgment", "shall", "be"];
const maxWidth2 = 16;
console.log(fullJustify(words2, maxWidth2));

复杂度分析

动态规划方法

• 时间复杂度：(O(n^2))，其中 n 是单词的数量。主要开销在于填充 cost 数组和进行动态规划计算。
• 空间复杂度：(O(n^2))，主要用于存储 cost 数组和 dp 数组。

递归回溯方法

• 时间复杂度：(O(2^n))，因为在最坏情况下，每个单词都有两种选择：放入当前行或放入下一行。
• 空间复杂度：(O(n))，主要是递归栈的空间开销。