68 Text Justification

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 words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
• For the last line of text, it should be left justified and no extra space is inserted between words.

For example,

words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note:

• Each word is guaranteed not to exceed L in length.
• Corner Cases: A line other than the last line might contain only one word. What should you do in this case? In this case, that line should be left-justified.

Solution

class Solution {
public:
    string justify(vector<string>& line, int maxWidth, int line_length) {
        int n = line.size();
        if ( n == 1 ) {
            while ( line[0].size() < maxWidth ) line[0] += " ";
            return line[0];
        }
        int left = maxWidth - line_length; 
        int add = left/(n - 1);
        int more = left - (n-1) * add;
        string spaces = "";
        for ( int i = 0; i <= add; i++ ) spaces += " ";
        string res = line[0];
        for ( int i = 1; i <= more; i++ ) res += spaces + " " + line[i];
        for ( int i = more+1; i <= n-1; i++ ) res += spaces + line[i];
        return res;
    }
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> res;
        int n = words.size();
        if ( n == 0 ) return res;
        if ( words[0].size() > maxWidth ) return res;
        vector<string> line;
        line.push_back(words[0]);
        int line_length = words[0].size();
        int icount = 1, nres = 1;
        for ( int i = 1; i <= n-1; i++ ) {
            if ( words[i].size() > maxWidth ) {res.clear(); return res;}
            if ( line_length + words[i].size() + 1 <= maxWidth ) { 
                line.push_back(words[i]);
                line_length += 1 + words[i].size();
                continue;
            }
            res.push_back(justify(line, maxWidth, line_length));
            line.clear();
            line.push_back(words[i]);
            line_length = words[i].size();
        }
        string tmp = line[0];
        for ( int i = 1; i <= int(line.size())-1; i++ ) tmp += " " + line[i];
        while ( tmp.size() != maxWidth ) tmp += " ";
        res.push_back(tmp);
        return res;
    }
};

Notes
Note for those "left-justified" line, you have to output a string that has a length of $$L$$ by appending extra spaces.