1 #include <iostream> 2 #include <cstdlib> 3 #include <string> 4 #include <vector> 5  6 using namespace std; 7  8 class Solution { 9 public:10     vector<string> fullJustify(vector<string> &words, int L) {11         int len = words.size();12         vector<string> res;13         if (L < 1) {14             res.push_back(string(""));15             return res;16         }17         int pos = 0;18 19         while (pos < len) {20             int pre_pos = pos;21             int llen = words[pos++].size();22 23             while (pos < len) {24                 if (llen + 1 + words[pos].length() > L) {25                     break;26                 }27                 llen = llen + 1 + words[pos++].length();28             }29             bool last_line = pos >= len;30             31             int wcnt = pos - pre_pos;       // number of words in one line32             int wlen = llen - (wcnt - 1);   // length of words in one line33             int space= L - wlen;            // space in one line34 35             string line;36             bool left_justify = last_line || wcnt == 1;37 38             // avg space if space can be distributed evenly, it should be a integer39             // or it will be a float and rounded to a integer40             int avg_space = 0;41             42             // when the avg space has been rounded, ext_space indicates the lost spaces43             int ext_space = 0;44             45             // be sure that zero divide will not happend46             // last line do not need avg_space and ext_space47             if (!left_justify) {48                 avg_space = space / (wcnt - 1);49                 ext_space = space - avg_space * (wcnt - 1);50             }51             // start to build a line52             line = words[pre_pos];53 54             for (int i=1; i<wcnt; i++) {55                 if (left_justify) {56                     line.push_back(‘ ‘);57                 } else {58                     line.append(string((ext_space-- > 0 ? 1 : 0) + avg_space, ‘ ‘));59                 }60                 line.append(words[pre_pos + i]);61             }62             if (line.size() < L) {63                 line.append(string(L - line.size(), ‘ ‘));64             }65             res.push_back(line);66         }67         68         return res;69     }70 };71 72 73 void print(vector<string>& s) {74     for (int i=0; i<s.size(); i++) {75         cout<<s[i]<<"|"<<endl;76     }77 }78 int main() {79     Solution s;80     const char* w[] = {"Listen","to","many,","speak","to","a","few."};81     vector<string> words(w, w + sizeof(w) / sizeof(const char*));82     words.push_back(string(""));83 84     vector<string> res = s.fullJustify(words, 6);85 86     print(res);87     system("pause");88     return 0;89 }