Text Justification
Given an array of words and a width, justify the text by adding spaces between words so that each line has exactly width characters. If a line cannot be justified, add spaces to the left of the line. The last line should be left-justified.
Constraints:
- 1 <= words.length <= 300
- 1 <= width <= 100
- 1 <= words[i].length <= 20
Examples:
Input: ["This", "is", "an", "example", "of", "text", "justification."]
Output: ["This is an", "example of text", "justification. "]
Explanation: The first line has 13 characters (This + is + an), so we add 4 spaces to the right. The second line has 15 characters (example + of + text), so we add 2 spaces to the right. The last line has 15 characters (justification), so we add 7 spaces to the right.
Solutions
Greedy Algorithm
The solution uses a greedy algorithm to justify the text. It iterates over the words and adds them to the current line. If the current line exceeds the maximum width, it justifies the current line and adds it to the result. The last line is left-justified.
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> result;
vector<string> currentLine;
int currentWidth = 0;
for (const string& word : words) {
if (currentWidth + word.length() + currentLine.size() > maxWidth) {
int spaces = maxWidth - currentWidth;
int gaps = currentLine.size() - 1;
if (gaps == 0) {
result.push_back(currentLine[0] + string(spaces, ' '));
}
else {
int spaceEachGap = spaces / gaps;
int extraSpaces = spaces % gaps;
string line;
for (int i = 0;
i < currentLine.size();
i++) {
line += currentLine[i];
if (i < currentLine.size() - 1) {
line += string(spaceEachGap + (i < extraSpaces ? 1 : 0), ' ');
}
}
result.push_back(line);
}
currentLine.clear();
currentLine.push_back(word);
currentWidth = word.length();
}
else {
currentLine.push_back(word);
currentWidth += word.length();
}
}
string lastLine;
for (const string& word : currentLine) {
lastLine += word + " ";
}
lastLine.resize(maxWidth, ' ');
result.push_back(lastLine);
return result;
}Follow-up:
How would you handle the case where the input words are not separated by spaces?
