Hard

题目描述

给你一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用"贪心算法"来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

注意：

  • 单词是指由非空格字符组成的字符序列。
  • 每个单词的长度大于 0，小于等于 maxWidth。
  • 输入单词数组 words 至少包含一个单词。

示例 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        "
]
解释: 注意最后一行的格式应为 "shall be    " 而不是 "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                  "
]

提示：

  • 1 <= words.length <= 300
  • 1 <= words[i].length <= 20
  • words[i] 由小写英文字母和符号组成
  • 1 <= maxWidth <= 100
  • words[i].length <= maxWidth

解题思路

这是一道模拟题，需要严格按照题目要求进行文本对齐。解题思路如下：

核心思想：

  1. 贪心分组：尽可能多地将单词放在一行中
  2. 空格分配：均匀分配单词间的空格，左侧优先
  3. 特殊处理：最后一行左对齐，单词行左对齐

算法步骤：

  1. 分组阶段：遍历单词数组，贪心地将尽可能多的单词放在当前行
  2. 对齐阶段：根据不同情况进行对齐处理：
    • 最后一行：左对齐，单词间用单个空格分隔，右侧补空格
    • 只有一个单词的行：左对齐，右侧补空格
    • 普通行：计算需要的总空格数，均匀分配给单词间隙

空格分配算法：

  • 计算总的额外空格数：maxWidth - 所有单词长度 - 最少空格数
  • 将额外空格均匀分配给 gaps = words.size() - 1 个间隙
  • 前 extraSpaces % gaps 个间隙各多分配一个空格

这种方法时间复杂度为 O(n)，其中 n 为所有字符的总数，空间复杂度为 O(1)（不考虑输出数组）。

代码实现

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> result;
        int i = 0;
        
        while (i < words.size()) {
            // 贪心地选择当前行的单词
            vector<string> currentWords;
            int currentLength = 0;
            
            while (i < words.size() && 
                   currentLength + words[i].length() + currentWords.size() <= maxWidth) {
                currentWords.push_back(words[i]);
                currentLength += words[i].length();
                i++;
            }
            
            // 构造当前行
            string line = justifyLine(currentWords, maxWidth, i == words.size());
            result.push_back(line);
        }
        
        return result;
    }
    
private:
    string justifyLine(vector<string>& words, int maxWidth, bool isLastLine) {
        if (words.size() == 1 || isLastLine) {
            // 左对齐
            string line = words[0];
            for (int i = 1; i < words.size(); i++) {
                line += " " + words[i];
            }
            line += string(maxWidth - line.length(), ' ');
            return line;
        }
        
        // 两端对齐
        int totalChars = 0;
        for (const string& word : words) {
            totalChars += word.length();
        }
        
        int totalSpaces = maxWidth - totalChars;
        int gaps = words.size() - 1;
        int spacesPerGap = totalSpaces / gaps;
        int extraSpaces = totalSpaces % gaps;
        
        string line = "";
        for (int i = 0; i < words.size() - 1; i++) {
            line += words[i];
            line += string(spacesPerGap + (i < extraSpaces ? 1 : 0), ' ');
        }
        line += words.back();
        
        return line;
    }
};

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        result = []
        i = 0
        
        while i < len(words):
            # 贪心地选择当前行的单词
            current_words = []
            current_length = 0
            
            while (i < len(words) and 
                   current_length + len(words[i]) + len(current_words) <= maxWidth):
                current_words.append(words[i])
                current_length += len(words[i])
                i += 1
            
            # 构造当前行
            line = self.justify_line(current_words, maxWidth, i == len(words))
            result.append(line)
        
        return result
    
    def justify_line(self, words, maxWidth, is_last_line):
        if len(words) == 1 or is_last_line:
            # 左对齐
            line = ' '.join(words)
            line += ' ' * (maxWidth - len(line))
            return line
        
        # 两端对齐
        total_chars = sum(len(word) for word in words)
        total_spaces = maxWidth - total_chars
        gaps = len(words) - 1
        spaces_per_gap = total_spaces // gaps
        extra_spaces = total_spaces % gaps
        
        line = ""
        for i in range(len(words) - 1):
            line += words[i]
            line += ' ' * (spaces_per_gap + (1 if i < extra_spaces else 0))
        line += words[-1]
        
        return line

public class Solution {
    public IList<string> FullJustify(string[] words, int maxWidth) {
        List<string> result = new List<string>();
        int i = 0;
        
        while (i < words.Length) {
            // 贪心地选择当前行的单词
            List<string> currentWords = new List<string>();
            int currentLength = 0;
            
            while (i < words.Length && 
                   currentLength + words[i].Length + currentWords.Count <= maxWidth) {
                currentWords.Add(words[i]);
                currentLength += words[i].Length;
                i++;
            }
            
            // 构造当前行
            string line = JustifyLine(currentWords, maxWidth, i == words.Length);
            result.Add(line);
        }
        
        return result;
    }
    
    private string JustifyLine(List<string> words, int maxWidth, bool isLastLine) {
        if (words.Count == 1 || isLastLine) {
            // 左对齐
            string line = string.Join(" ", words);
            line += new string(' ', maxWidth - line.Length);
            return line;
        }
        
        // 两端对齐
        int totalChars = words.Sum(word => word.Length);
        int totalSpaces = maxWidth - totalChars;
        int gaps = words.Count - 1;
        int spacesPerGap = totalSpaces / gaps;
        int extraSpaces = totalSpaces % gaps;
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < words.Count - 1; i++) {
            sb.Append(words[i]);
            sb.Append(new string(' ', spacesPerGap + (i < extraSpaces ? 1 : 0)));
        }
        sb.Append(words[words.Count - 1]);
        
        return sb.ToString();
    }
}

var fullJustify = function(words, maxWidth) {
    const result = [];
    let i = 0;
    
    while (i < words.length) {
        let line = [];
        let lineLength = 0;
        
        // Pack words into current line
        while (i < words.length && lineLength + words[i].length + line.length <= maxWidth) {
            lineLength += words[i].length;
            line.push(words[i]);
            i++;
        }
        
        // Format the line
        if (i === words.length) {
            // Last line - left justify
            let justified = line.join(' ');
            justified += ' '.repeat(maxWidth - justified.length);
            result.push(justified);
        } else if (line.length === 1) {
            // Single word line
            let justified = line[0] + ' '.repeat(maxWidth - line[0].length);
            result.push(justified);
        } else {
            // Multiple words - full justify
            let totalSpaces = maxWidth - lineLength;
            let gaps = line.length - 1;
            let spacesPerGap = Math.floor(totalSpaces / gaps);
            let extraSpaces = totalSpaces % gaps;
            
            let justified = '';
            for (let j = 0; j < line.length; j++) {
                justified += line[j];
                if (j < gaps) {
                    justified += ' '.repeat(spacesPerGap);
                    if (j < extraSpaces) {
                        justified += ' ';
                    }
                }
            }
            result.push(justified);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
整体O(n)O(1)

说明：

  • 时间复杂度： O(n)，其中 n 是所有字符的总数。每个单词和字符都只被处理一次
  • 空间复杂度： O(1)，除了存储结果的数组外，只使用了常数额外空间

相关题目