68. 文本左右对齐

参考68. 文本左右对齐 - 力扣（Leetcode）。

题目

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

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

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

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

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

解题思路

• 模拟：考虑模拟一行一行的放置单词,主要处理每行放多少单词以及两端对齐时空格数量的计算,注释代码如下所示。

模拟 0ms

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        //考虑模拟一行一行的放
        List<String> ans = new ArrayList<>();
        int wordIndex = 0;
        while(wordIndex < words.length) {
            int count = 1,len = words[wordIndex].length();
            for(int i = wordIndex + 1; i < words.length; i++) {
                if(len + 1 + words[i].length() > maxWidth) break;
                len += 1 + words[i].length();
                count ++;
            }
            StringBuilder sb = new StringBuilder();
            if(count == 1) { //只有一个单词
                sb.append(words[wordIndex]);
                //补空格
                for(int i = 0; i < maxWidth - words[wordIndex].length(); i++)
                    sb.append(' ');
            } else if(wordIndex + count == words.length || maxWidth == len) {
                //最后一行 或者刚好间隔一个空格
                for(int i = 0; i < count; i++) {
                    if(sb.length() > 0) sb.append(' ');
                    sb.append(words[wordIndex + i]);
                }
                //补空格
                for(int i = 0,sbLen = sb.length(); i < maxWidth - sbLen; i++)
                    sb.append(' ');
            }else { //两边对齐
                //计算空格长度
                int spaceLen = (maxWidth - len + count - 1)/(count - 1);
                int leftSpace = maxWidth - len + count - 1 - (count - 1) * spaceLen;
                StringBuilder spaces = new StringBuilder(spaceLen);
                for(int i = 0; i < spaceLen; i++)
                    spaces.append(' ');
                for(int i = 0; i < count; i++) {
                    if(sb.length() > 0){
                        sb.append(spaces); //插入空格 和多余空格
                        if(leftSpace-- > 0) sb.append(' ');
                    }
                    sb.append(words[wordIndex + i]);
                }
            }
            ans.add(sb.toString());
            wordIndex += count;
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n)，n为所有单词长度之和。
• 空间复杂度：O(k)，k为StringBuilder使用空间maxWidth。