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.
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> result = new ArrayList<>();
List<String> currentLine = new ArrayList<>();
int currentWidth = 0;
for (String word : words) {
if (currentWidth + word.length() + currentLine.size() > maxWidth) {
int spaces = maxWidth - currentWidth;
int gaps = currentLine.size() - 1;
if (gaps == 0) {
result.add(currentLine.get(0) + repeat(" ", spaces));
}
else {
int spaceEachGap = spaces / gaps;
int extraSpaces = spaces % gaps;
StringBuilder line = new StringBuilder();
for (int i = 0;
i < currentLine.size();
i++) {
line.append(currentLine.get(i));
if (i < currentLine.size() - 1) {
line.append(repeat(" ", spaceEachGap + (i < extraSpaces ? 1 : 0)));
}
}
result.add(line.toString());
}
currentLine.clear();
currentLine.add(word);
currentWidth = word.length();
}
else {
currentLine.add(word);
currentWidth += word.length();
}
}
StringBuilder lastLine = new StringBuilder();
for (String word : currentLine) {
lastLine.append(word).append(" ");
}
lastLine.setLength(maxWidth);
result.add(lastLine.toString());
return result;
}
private String repeat(String str, int count) {
StringBuilder sb = new StringBuilder();
for (int i = 0;
i < count;
i++) {
sb.append(str);
}
return sb.toString();
}Follow-up:
How would you handle the case where the input words are not separated by spaces?
