# 68 - Text Justification

解法一 - 算出每一行可以塞多少字，然後再補 space

基本上就是一個 greedy 的思想，能塞多少就盡量塞，剩下的才用 space 補足。

要注意的地方就是規則比較複雜一點：

1. 每塞入一個 word 至少要跟著一個空白，所以如果有兩個字長度加起來 == maxWidth，那也不能算是可以塞在同一行

2. 除了最後一行之外，每個字之間的空白至少是 (maxWidth - l) / (k - 1)。但如果無法除盡，那就需要額外再處理剩下的 (maxWidth - l) % (k - 1)。

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> res;

        // Let i to i+k-1 words be put in the same sentence
        // use l to record current length of words and corresponding spaces
        int k, l;
        for(int i=0; i<words.size(); i+=k) {
            // Determine how many words can we put in this sentence
            for(k=l=0; i+k<words.size() && l+words[i+k].length()<=maxWidth-k; k++) {
                l += words[i+k].size();
            }

            // Starting putting words into current sentence
            string tmp = words[i];
            for(int j = 0; j < k - 1; j++) {
                // This line of code is for last line 
                // E.g. the last line is "shall be    " 
                // instead of "shall     be",
                // because the last line must be left-justified.
                if(i + k >= words.size()) tmp += " ";

                // Distribute space evenly by (maxWidth - l) / (k - 1)
                // if there are more spaces which cannot be distributed evenly
                // We can know how many more spaces need to be put by (maxWidth - l) % (k - 1)
                // then if j < (maxWidth - l) % (k - 1), we need to put one more space
                else tmp += string((maxWidth - l) / (k - 1) + (j < (maxWidth - l) % (k - 1)), ' ');

                tmp += words[i+j+1];
            }
            // Put spaces if tmp is not as long as maxWidth
            tmp += string(maxWidth - tmp.size(), ' ');

            // Push current sentence into answer
            res.push_back(tmp);
        }

        return res;
    }
};