Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified. You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters. Extra spaces between w…

leetcode_text_justification.cpp

class Solution {
public:
    vector<string> fullJustify(vector<string> &words, int L) {
        vector<string> ret;
        int n = words.size();
        int pos = 0;
        while (pos < n) {
            int len = words[pos].length();
            int next = -1;
            for (int i = pos + 1; i < n; ++i) {
                if (len + words[i].length() + 1 <= L)
                    len += words[i].length() + 1;
                else {
                    next = i;
                    break;
                }
            }
            if (next == -1)
                next = n;
            int cnt = next - pos;
            int spaces = next == n ? cnt - 1 : L - len + cnt - 1;
            string buf;
            for (int i = pos; i < next; ++i) {
                buf.append(words[i]);
                int t = 0;
                if (cnt == 1)
                    t = spaces;
                else if (i != next - 1)
                    t = spaces / (cnt - 1) + (spaces % (cnt - 1) > i - pos);
                while (t--)
                    buf.append(" ");
            }
            if (next == n) {
                for (int i = 0; i < L - len; ++i)
                    buf.append(" ");
            }
            pos = next;
            ret.push_back(buf);
        }
        return ret;
    }
};