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 exactlyL 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.

非常不错的题目，直接考了word或其他文本编辑器的两边对齐功能的实现。

基本思路是依次添加一个单词进来，计算在每个单词间加入一个空格的总长度，如果总长度大于了规定的L，则丢掉最后遇到的单词，把总长度小于L的单词丢入justifyOneLine的函数中，进行单行的排版。

对于最末一行，需要单独编程考虑，因为它是左对齐。

这里要注意，即使是左对齐，也要在字符串右侧padding（添加空格）到L长度。

在justifyOneLine函数中，先计算单词总长度，再计算需要填补的空格数，再用空格数除以单词数-1，即单词间的间隔数，获取每个间隔所应该填充的基础空格数。因为可能有余数，所以优先在左侧的间隔多添加一个空格。

编程中我出现了3个bug

1. line 26, 当前的单词超出一行限制时，需要丢掉该单词，这里应该有一个it–；因为我们并没有处理该单词，如果落掉了it–的话，就会漏掉一些单词。

2. line 65，不确定运算顺序时，最保险的方法是加括号。

3. line 31-43，对于最后一行的处理，需要左对齐，单独处理。

class Solution {
public:
    vector<string> fullJustify(vector<string> &words, int L) {
        vector<string> re;
        vector<string>::iterator it = words.begin();
        vector<string>::iterator startIt;
        size_t length = 0;
        while(it != words.end()){
            //it's the first word, question guarantee it's shorter than L
            if(length == 0){
                length = (*it).size();
                startIt = it;
            }
            // not the first word
            else{
                //'*it' can be filled in one line
                if(length + (*it).size() + 1 <= L){
                    length += (*it).size() + 1;
                }
                //length exceed if *it is included 
                //justify them in one line
                else{
                    re.push_back(justifyOneLine(startIt, it, L));
                    startIt = it;
                    length = 0;
                    it--;// 1st bug
                }
            }
            it++;
        }
        //3rd bug here, last line should be left justified
        //push the last line to re.
        string str;
        str = *startIt;
        startIt++;
        while(startIt != it){
            str.push_back(' ');
            str.append(*startIt);
            startIt++;
        }
        //3rd bug, padding the last line to L
        str.append(L - str.size(), ' ');
        re.push_back(str);
        return re;
    }
    string justifyOneLine(vector<string>::iterator start, vector<string>::iterator end, int length){
        string re;
        //only one word, left justify
        if(end - start == 1){
            re.append(*start);
            re.append(length - (*start).size(), ' ');
        }
        // more than one word cram in one line
        else{
            int numOfWords = end - start;
            int lengthOfWords = 0;
            for(vector<string>::iterator it = start; it != end; it++){
                lengthOfWords += (*it).size();
            }
            int numOfPadding = length - lengthOfWords;
            int baseGap = numOfPadding / (numOfWords - 1);
            int numOfExtraGap = numOfPadding % (numOfWords - 1);
            re.append(*start);
            for(vector<string>::iterator it = start + 1; it != end; it++){
                int gap = baseGap + (numOfExtraGap-- > 0? 1: 0); // 2nd bug, add parethese here
                re.append(gap, ' ');
                re.append(*it);
            }
        }
        return re;
    }
};