-
Notifications
You must be signed in to change notification settings - Fork 1
/
0068.cpp
93 lines (79 loc) · 2.16 KB
/
0068.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
if (words.empty())
return {};
// creates lines
vector<vector<string>> text;
vector<string> line;
while (!words.empty())
{
auto w = words.front();
words.erase(words.begin());
if (line.empty())
{
line = { w };
}
else
{
auto used = 0;
for (auto l : line)
used += l.size();
used += line.size() - 1;
if (used + 1 + w.size() > maxWidth)
{
text.push_back(line);
line = { w };
}
else
{
line.push_back(w);
}
}
}
if (!line.empty())
text.push_back(line);
// justify
vector<string> result;
for (int i = 0; i < text.size() - 1; i++)
{
auto& l = text[i];
// single word
if (l.size() == 1)
{
auto one = l.front();
while (one.size() < maxWidth)
one += ' ';
result.push_back(one);
continue;
}
int need = maxWidth;
for (auto w : l)
need -= w.size();
string line = l.front();
for (int j = 1; j < l.size(); j++)
{
int all = need / (l.size() - 1);
int extra = need % (l.size() - 1);
while (all-- > 0)
line += ' ';
if (extra >= j)
line += ' ';
line += l[j];
}
result.push_back(line);
}
// last line
string last;
for (auto l : text.back())
{
if (!last.empty())
last += ' ';
last += l;
}
while (last.size() < maxWidth)
last += ' ';
result.push_back(last);
return result;
}
};