题目

题解

  • 时间复杂度$O(N)$
  • 空间复杂度$O(maxWidth+N)$，用于暂存每行的结果和存结果
class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> res;
        if(words.empty()) return res;
        int left = 0;//存每一行起点string的下标
        while(left < words.size()){
            //right存每一行最后一个字符串的下标，tmp_width存该行当前所有字符串的长度，不包括空格
            int right = left, tmp_width = 0;
            //注意第二个条件，前两个值是n+1个字符串的长度，确定n+1不超出再加上right的字符，right-left是每个字符串之间有一个空格
            while(right < words.size() && tmp_width+words[right].size()+right-left <= maxWidth){
                tmp_width += words[right++].size();
            }//找到该行最右字符串的下标

            ////下面这一块用于在每一行添加字符串和空格
            string line;//存每行的字符串和空格
            int space = maxWidth - tmp_width;//存每行空格总个数
            for(int i=left; i<right; ++i){//遍历当前行的每个字符串
                int tmp_space = 0;//存该处填入的空格数
                line += words[i];//先接上下个字符串
                ////下面这一块计算每个字符串中间的空格
                if(right == words.size()){//最后一行，前面每个字符串添0，后面直接加上所有空格
                    if(i == right-1) tmp_space = space;
                    else tmp_space = 1;
                }else if(i != right-1){//其他行的最后一个字符串之前，若空格可整除空位置数，就每个空位置均匀放空格，否则左边的空位置多放一个
                    if(space%(right-i-1) == 0) tmp_space = space/(right-i-1);
                    else tmp_space = space/(right-i-1)+1;
                }else tmp_space = space;//最后一个字符串添加的空格数，一般space为0，除了只有一个字符串的行，需要添加所有空格
                line.append(tmp_space, ' ');//在line中添加tmp_space个空格，注意第二个参数要用字符char
                space -= tmp_space;//space减去已经添加的空格数
            }
            res.push_back(line);
            left = right;//更新左界限
        }
        return res;
    }
};