68. 文本左右對齊

給定一個單詞數組 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



class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<String>();
        int right = 0, n = words.length;
        while (true) {
            int left = right; // 當前行的第一個單詞在 words 的位置
            int sumLen = 0; // 統計這一行單詞長度之和
            // 循環確定當前行可以放多少單詞，注意單詞之間應至少有一個空格
            while (right < n && sumLen + words[right].length() + right - left <= maxWidth) {
                sumLen += words[right++].length();
            }

            // 當前行是最後一行：單詞左對齊，且單詞之間應只有一個空格，在行末填充剩餘空格
            if (right == n) {
                StringBuffer sb = join(words, left, n, " ");
                sb.append(blank(maxWidth - sb.length()));
                ans.add(sb.toString());
                return ans;
            }

            int numWords = right - left;
            int numSpaces = maxWidth - sumLen;

            // 當前行只有一個單詞：該單詞左對齊，在行末填充剩餘空格
            if (numWords == 1) {
                StringBuffer sb = new StringBuffer(words[left]);
                sb.append(blank(numSpaces));
                ans.add(sb.toString());
                continue;
            }

            // 當前行不只一個單詞
            int avgSpaces = numSpaces / (numWords - 1);
            int extraSpaces = numSpaces % (numWords - 1);
            StringBuffer sb = new StringBuffer();
            sb.append(join(words, left, left + extraSpaces + 1, blank(avgSpaces + 1))); // 拼接額外加一個空格的單詞
            sb.append(blank(avgSpaces));
            sb.append(join(words, left + extraSpaces + 1, right, blank(avgSpaces))); // 拼接其餘單詞
            ans.add(sb.toString());
        }
    }

    // blank 返回長度為 n 的由空格組成的字符串
    public String blank(int n) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < n; ++i) {
            sb.append(' ');
        }
        return sb.toString();
    }

    // join 返回用 sep 拼接 [left, right) 範圍內的 words 組成的字符串
    public StringBuffer join(String[] words, int left, int right, String sep) {
        StringBuffer sb = new StringBuffer(words[left]);
        for (int i = left + 1; i < right; ++i) {
            sb.append(sep);
            sb.append(words[i]);
        }
        return sb;
    }
}