68 文本左右对齐

🚀 相关链接

LeetCode 68 - 文本左右对齐

📜 描述

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

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

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

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

💡 示例

示例 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                  "
  ]

📝 提示

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

💭 思路

1. 贪心算法：尽可能多地往每行中放置单词，直到无法再放置下一个单词为止。
2. 均匀分配空格：对于非最后一行，尽可能均匀分配单词间的空格数量，如果无法均匀分配，则左侧的空格数要多于右侧的空格数。
3. 最后一行左对齐：对于最后一行，单词之间不插入额外的空格，直接在右侧填充空格以满足 maxWidth 的要求。

💻 代码实现

public List<String> fullJustify(String[] words, int maxWidth) {
    List<String> res = new ArrayList<>();
    int i = 0;
    StringBuilder sb = new StringBuilder();
    while(i < words.length){
        String word = words[i];
        if (sb.isEmpty()){
            if (maxWidth >= word.length()){
                sb.append(word);
                i++;
            }
        }else{
            if (maxWidth >= sb.length() + word.length() + 1){
                sb.append(" ").append(word);
                i++;
            }else{
                res.add(sb.toString());
                sb = new StringBuilder();
            }
        }
        if (i >= words.length){
            res.add(sb.toString());
        }
    }
    for (int j = 0; j < res.size(); j++) {
        String s = res.get(j);
        if (j == res.size() - 1 && s.length() < maxWidth){
            res.set(j, s + " ".repeat(maxWidth - s.length()));
        }else if (j < res.size() - 1){
            if (s.length() < maxWidth){
                res.set(j, adjustSpaces(s, maxWidth));
            }
        }
    }
    return res;
}

public String adjustSpaces(String s, int maxWidth) {
    String[] words = s.split(" ");
    int wordCount = words.length;

    if (wordCount == 1) {
        StringBuilder single = new StringBuilder(words[0]);
        while (single.length() < maxWidth) {
            single.append(' ');
        }
        return single.toString();
    }

    int sumWordLengths = 0;
    for (String w : words) {
        sumWordLengths += w.length();
    }

    int totalSpaces = maxWidth - sumWordLengths;
    int gaps = wordCount - 1;

    int extraPerGap = totalSpaces / gaps;
    int remainder = totalSpaces % gaps;

    StringBuilder result = new StringBuilder();
    for (int i = 0; i < gaps; i++) {
        result.append(words[i]);
        int spacesToAdd = extraPerGap;
        if (i < remainder) {
            spacesToAdd++;
        }
        for (int k = 0; k < spacesToAdd; k++) {
            result.append(' ');
        }
    }
    result.append(words[gaps]);

    return result.toString();
}