給定一個(gè)單詞數(shù)組 words 和一個(gè)長(zhǎng)度 maxWidth ，重新排版單詞，使其成為每行恰好有 maxWidth 個(gè)字符，且左右兩端對(duì)齊的文本。 你應(yīng)該使用 “貪心算法” 來(lái)放置給定的單詞；也就是說(shuō)，盡可能多地往每行中放置單詞。必要時(shí)可用空格 ' ' 填充，使得每行恰好有 maxWidth 個(gè)字符。 要求盡可能均勻分配單詞間的空格數(shù)量。如果某一行單詞間的空格不能均勻分配，則左側(cè)放置的空格數(shù)要多于右側(cè)的空格數(shù)。 文本的最后一行應(yīng)為左對(duì)齊，且單詞之間不插入額外的空格。 注意: 單詞是指由非空格字符組成的字符序列。 每個(gè)單詞的長(zhǎng)度大于 0，小于等于 maxWidth。 輸入單詞數(shù)組 words 至少包含一個(gè)單詞。?

方法一：基本貪心算法實(shí)現(xiàn)

function fullJustify(words: string[], maxWidth: number): string[] {let result: string[] = [];let i = 0;while (i < words.length) {let lineWords: string[] = [];let currentLength = 0;// 盡可能多地往當(dāng)前行添加單詞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) {// 最后一行或只有一個(gè)單詞的行，左對(duì)齊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;
}// 測(cè)試示例
let words = ["This", "is", "an", "example", "of", "text", "justification."];
let maxWidth = 16;
let result = fullJustify(words, maxWidth);
console.log(result);

方法二：拆分邏輯實(shí)現(xiàn)

function fullJustify(words: string[], maxWidth: number): string[] {let result: string[] = [];let start = 0;while (start < words.length) {let end = start;let lineLength = 0;// 確定當(dāng)前行能容納的單詞范圍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) {// 最后一行或只有一個(gè)單詞的行，左對(duì)齊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;
}// 測(cè)試示例
let words2 = ["What", "must", "be", "acknowledgment", "shall", "be"];
let maxWidth2 = 16;
let result2 = fullJustify(words2, maxWidth2);
console.log(result2);

方法三：利用輔助函數(shù)實(shí)現(xiàn)

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) {// 最后一行或只有一個(gè)單詞的行，左對(duì)齊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;// 確定當(dāng)前行能容納的單詞范圍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;
}// 測(cè)試示例
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);

復(fù)雜度分析

• 時(shí)間復(fù)雜度：三種方法的時(shí)間復(fù)雜度均為?(O(n))，其中?n?是單詞數(shù)組?words?中所有字符的總數(shù)。因?yàn)槊總€(gè)單詞只會(huì)被處理一次。
• 空間復(fù)雜度：三種方法的空間復(fù)雜度均為?(O(m))，其中?m?是結(jié)果數(shù)組的長(zhǎng)度，主要用于存儲(chǔ)排版后的每行文本。

這些方法的核心思路都是貪心算法，盡可能多地往每行中放置單詞，然后根據(jù)不同情況（最后一行或非最后一行）來(lái)分配空格。不同方法只是在代碼結(jié)構(gòu)和實(shí)現(xiàn)細(xì)節(jié)上有所差異。

方法四：動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃的核心在于將大問(wèn)題拆解為小問(wèn)題，通過(guò)保存子問(wèn)題的解來(lái)避免重復(fù)計(jì)算。對(duì)于這個(gè)單詞排版問(wèn)題，我們可以定義狀態(tài)并找出狀態(tài)轉(zhuǎn)移方程。

function fullJustify(words: string[], maxWidth: number): string[] {const n = words.length;// cost[i][j] 表示從第 i 個(gè)單詞到第 j 個(gè)單詞放在一行的代價(jià)const cost: number[][] = new Array(n).fill(0).map(() => new Array(n).fill(Number.MAX_SAFE_INTEGER));// 計(jì)算每行放置不同單詞組合的代價(jià)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 個(gè)單詞開(kāi)始排版的最小代價(jià)const dp: number[] = new Array(n + 1).fill(Number.MAX_SAFE_INTEGER);// 用于記錄每個(gè)位置的最優(yōu)分割點(diǎn)const path: number[] = new Array(n + 1).fill(0);dp[n] = 0;// 動(dòng)態(tài)規(guī)劃計(jì)算最小代價(jià)和最優(yōu)分割點(diǎn)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;// 根據(jù)最優(yōu)分割點(diǎn)構(gòu)建排版結(jié)果while (start < n) {const end = path[start];const lineWords = words.slice(start, end);let line = "";if (end === n) {// 最后一行左對(duì)齊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;
}// 測(cè)試示例
const words = ["This", "is", "an", "example", "of", "text", "justification."];
const maxWidth = 16;
console.log(fullJustify(words, maxWidth));

方法五：遞歸回溯

遞歸回溯是一種通過(guò)嘗試所有可能的組合來(lái)找到最優(yōu)解的方法。對(duì)于這個(gè)問(wèn)題，我們可以遞歸地嘗試將單詞放入不同的行，直到找到滿(mǎn)足條件的排版方式。

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;// 盡可能多地往當(dāng)前行添加單詞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) {// 最后一行左對(duì)齊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;
}// 測(cè)試示例
const words2 = ["What", "must", "be", "acknowledgment", "shall", "be"];
const maxWidth2 = 16;
console.log(fullJustify(words2, maxWidth2));

復(fù)雜度分析

動(dòng)態(tài)規(guī)劃方法

• 時(shí)間復(fù)雜度：(O(n^2))，其中?n?是單詞的數(shù)量。主要開(kāi)銷(xiāo)在于填充?cost?數(shù)組和進(jìn)行動(dòng)態(tài)規(guī)劃計(jì)算。
• 空間復(fù)雜度：(O(n^2))，主要用于存儲(chǔ)?cost?數(shù)組和?dp?數(shù)組。

遞歸回溯方法

• 時(shí)間復(fù)雜度：(O(2^n))，因?yàn)樵谧顗那闆r下，每個(gè)單詞都有兩種選擇：放入當(dāng)前行或放入下一行。
• 空間復(fù)雜度：(O(n))，主要是遞歸棧的空間開(kāi)銷(xiāo)。