题目描述

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

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

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

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

说明:

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

样例

示例:
输入:
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

(模拟) $O(n * maxWidth)$

字符串模拟题，没啥技巧，只能细心调；
处理分三种情况，一行多个单词、一行一个单词、最后一行;
第一遍写为了实现方便，多开了一个vector tmp，可以使用两个变量记录单词读取的起始位置，来优化掉这部分空间。

时间复杂度

最差情况，每个单词一行，一行$maxWidth$个字符，所以复杂度为$O(n * maxWidth)$。

参考文献

C++ 代码

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        if (words.empty()) return {};
        vector<string> res;

        int word_idx = 0, n = words.size();
        while (word_idx < n){
            vector<string> tmp; tmp.push_back(words[word_idx++]);
            int cur_len = tmp[0].size(), len_wo_space = tmp[0].size();
            while (word_idx < n && cur_len + 1 + words[word_idx].size() <= maxWidth){
                cur_len += words[word_idx].size() + 1;
                len_wo_space += words[word_idx].size();
                tmp.push_back(words[word_idx++]);
            }
            string str = tmp[0];

            // 最后一行
            if (word_idx >= n){
                for (int i = 1; i < tmp.size(); ++i) str += ' ' + tmp[i];
                str += string(maxWidth - str.size(), ' ');
            }
            // 多个单词
            else if (tmp.size() > 1){
                int spaces = (maxWidth - len_wo_space) / (tmp.size() - 1), 
                more = (maxWidth - len_wo_space) % (tmp.size() - 1);
                for (int i = 1; i < tmp.size(); ++i){
                    str += string(spaces, ' ');
                    if (i <= more) str += ' ';
                    str += tmp[i];
                }
            }
            // 一个单词
            else str += string(maxWidth - tmp[0].size(), ' ');
            res.push_back(str);
        }

        return res;
    }
};

将vector tmp优化掉，节省空间

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        if (words.empty()) return {};
        vector<string> res;

        int l = 0, word_idx = 0, n = words.size();
        while (word_idx < n){
            int cur_len = words[word_idx].size(), len_wo_space = words[word_idx].size(); ++word_idx;
            while (word_idx < n && cur_len + 1 + words[word_idx].size() <= maxWidth){
                cur_len += words[word_idx].size() + 1;
                len_wo_space += words[word_idx].size();
                ++word_idx;
            }
            string str = words[l];

            if (word_idx >= n){
                for (int i = l + 1; i < word_idx; ++i) str += ' ' + words[i];
                str += string(maxWidth - str.size(), ' ');
            }
            else if (word_idx - l > 1){
                int spaces = (maxWidth - len_wo_space) / (word_idx - l - 1), 
                more = (maxWidth - len_wo_space) % (word_idx - l - 1);
                for (int i = l + 1; i < word_idx; ++i){
                    str += string(spaces, ' ');
                    if (i - l <= more) str += ' ';
                    str += words[i];
                }
            }
            else str += string(maxWidth - words[l].size(), ' ');
            res.push_back(str);
            l = word_idx;
        }

        return res;
    }
};