Text Justification Algorithm
In typesetting and page layout, alignment or range is the setting of text flow or picture placement relative to a page, column (measure), table cell, or tab. The type alignment setting is sometimes referred to as text alignment, text justification, or type justification. continuous casting typesetting systems such as the Linotype were able to reduce the jaggedness of the right-hand sides of adjacent lines of flush left composition by inserting self-adjusting space bands between words to evenly distribute white space, take excessive space that would have happened at the end of the line and redistributing it between words. graphic designers and typesetters use desktop systems also have the option, though rarely used, to adjust word and letter spacing, or" tracking", on a manual line-by-line basis to achieve more even overall spacing. In flush left text, words are separated on a line by the default word space build into the font.
class Solution {
public:
vector<string> fullJustify(vector<string>& words, int L) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<int> needed_lines(words.size(), 0);
int count_line = 1;
int len = 0;
for (int i = 0; i < words.size(); i++) {
if (len + words[i].size() + 1 <= L + 1) {
needed_lines[i] = count_line;
len += words[i].size() + 1;
}
else {
count_line += 1;
len = words[i].size() + 1;
needed_lines[i] = count_line;
}
}
vector<string> justified;
int start = 0;
while (start < words.size()) {
int end = start + 1;
int words_len = words[start].size();
while (end < words.size() && needed_lines[start] == needed_lines[end]) {
words_len += words[end].size();
end += 1;
}
int words_num = end - start;
string justified_line;
if (words_num == 1) {
justified_line += words[start];
justified_line.append(L - words_len, ' ');
}
else {
int extra = (L - words_len) % (words_num - 1);
int blank = (L - words_len) / (words_num - 1);
if (end == words.size()) {
extra = 0; blank = 1;
}
for (int i = start; i < end; i++) {
justified_line += words[i];
if (i == end -1) continue;
if (extra > 0) {
justified_line.append(blank + 1, ' ');
extra -= 1;
}
else
justified_line.append(blank, ' ');
}
if (end == words.size()) {
justified_line.append(L - words_len - words_num + 1, ' ');
}
}
justified.push_back(justified_line);
start = end;
}
return justified;
}
};
