Leetcode 68. Text Justification

题目链接：https://leetcode.com/problems/text-justification/

题目大意

给出一串单词和每行宽度，要求在单词中塞入空格使之两端对齐并且排版每行为指定宽度。其中每行应该尽可能多的放入单词，单词间的空格应平均分配。无法平分时，左边空格数大于右边空格。最后一行左对齐。

思路

首先遍历所有单词，找出应在一行的单词。依次判断当前行能否塞下下个单词即可。需要注意加入新的单词就意味着至少有一个空格，应把空格加入当前行的长度计算。

确定好每行的单词后，就开始往里塞空格。先平均分配空格，然后计算多余的空格，加在左边的单词中间。然后最后一行因为是左对齐，单独处理就行了。

代码

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        int maxlen=words.size();
        vector<vector<string>> lines(maxlen);
        vector<string> result;
        int linelen[maxlen];
        fill(linelen,linelen+maxlen,0);
        int cur=0,len=0;
        for(int i=0;i<maxlen;){
            if(words[i].length()+len<=maxWidth){
                lines[cur].push_back(words[i]);
                len+=words[i].length();
                len++;
                linelen[cur]+=words[i].length();
                i++;
            }else{
                cur++;
                len=0;
            }
        }
        for(int i=0;i<cur;i++){
            int spaces=maxWidth-linelen[i];
            int avgspace,addup;
            if(lines[i].size()>1){
                avgspace=spaces/(lines[i].size()-1);
                addup=spaces-avgspace*(lines[i].size()-1);
            }
            else{
                avgspace=spaces;
                addup=0;
            }
            string line="",sp="";
            for(int j=0;j<avgspace;j++)
                sp+=" ";
            for(int j=0;j<lines[i].size();j++){
                line+=lines[i][j];
                if(j!=lines[i].size()-1||j==0)
                    line+=sp;
                if(addup>0){
                    line+=" ";
                    addup--;
                }
            }
            result.push_back(line);
        }
        string line="";
        for(int i=0;i<lines[cur].size();i++){
            line+=lines[cur][i];
            if(i!=lines[cur].size()-1)
                line+=" ";
        }
        for(int i=line.size();i<maxWidth;i++)
            line+=" ";
        result.push_back(line);
        return result;
    }
};