LeetCode Text Justification

 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 line
32             int wlen = llen - (wcnt - 1);   // length of words in one line
33             int space= L - wlen;            // space in one line
34 
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 integer
39             // or it will be a float and rounded to a integer
40             int avg_space = 0;
41             
42             // when the avg space has been rounded, ext_space indicates the lost spaces
43             int ext_space = 0;
44             
45             // be sure that zero divide will not happend
46             // last line do not need avg_space and ext_space
47             if (!left_justify) {
48                 avg_space = space / (wcnt - 1);
49                 ext_space = space - avg_space * (wcnt - 1);
50             }
51             // start to build a line
52             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 }