Description

Submission

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        int width = 0;
        int widthWithoutSpace = 0;
        int start = 0;
        vector<string> res;
        for(int i = 0; i < words.size(); ++i) {
            if(width == 0) {
                width += words[i].size();
                widthWithoutSpace += words[i].size();
                start = i;
            } else {
                if(width + 1 + words[i].size() > maxWidth) {
                    // [start, i) => [start, i - 1]
                    int spaces = maxWidth - widthWithoutSpace;
                    string line = "";
                    if(start == i - 1) {
                        line += words[start];
                        line += string(maxWidth - words[start].size(), ' ');
                    } else {
                        for (int j = start; j < i; ++j) {
                            line += words[j];
                            if (j != i - 1) {
                                int gap = i - 1 - j;
                                int space;
                                if (spaces % gap == 0) {
                                    space = spaces / gap;
                                } else {
                                    space = spaces / gap + 1;
                                }
                                spaces -= space;
                                line += string(space, ' ');
                            }
                        }
                    }
                    res.push_back(line);
                    width = 0;
                    widthWithoutSpace = 0;
                    --i;
                } else {
                    width += (1 + words[i].size());
                    widthWithoutSpace += words[i].size();
                }
            }
        }
        if(width != 0) {
            string line = "";
            int count = 0;
            for(int i = start; i < words.size(); ++i) {
                line += words[i];
                count += words[i].size();
                if(i != words.size() - 1) {
                    line += " ";
                    count++;
                }
            }
            line += string(maxWidth - count, ' ');
            res.push_back(line);
        }
        return res;
    }
};