This page explains Java solution to problem Text Justification
using Greedy algorithm
.
Given an array of words
and a width maxWidth
, format the text such that each line has exactly maxWidth
characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words. Example 1:Example 2:Input: words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
Output: [
"This is an",
"example of text",
"justification. " ]
Input: words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
Output: [
"What must be",
"acknowledgment ",
"shall be " ]
package com.vc.hard;
import java.util.*;
class TextJustification {
public List<String> fullJustify(String[] words, int maxWidth) {
int index = 0;
int width = 0;
int widthWithoutSpace = 0;
int fitting = 0;
int start = 0;
List<String> res = new ArrayList<>();
while(index < words.length) {
if(width + words[index].length() <= maxWidth) {
width = Math.min(maxWidth, width + words[index].length() + 1);
widthWithoutSpace = widthWithoutSpace + words[index].length();
fitting++;
index++;
}
else {
format(words, width, widthWithoutSpace, maxWidth, start, fitting, res);
width = 0;
widthWithoutSpace = 0;
fitting = 0;
start = index;
}
}
if(fitting > 0) format(words, width, widthWithoutSpace, maxWidth, start, fitting, res);
return res;
}
private void format(String[] words, int width, int widthWithoutSpace, int maxWidth,
int start, int fitting,
List<String> res) {
/**
* We will want last line to be left justified
* So if it is only one word or if it is last line, just append one spaces
* And append remainingSpaces later
**/
if(fitting == 1 || start + fitting == words.length) {
StringBuilder sb = new StringBuilder();
int index = 0;
while(index < fitting) {
sb.append(words[start + index]);
if(index < fitting - 1) sb.append(" ");
index++;
}
int remainingSpaces = maxWidth - (widthWithoutSpace + fitting - 1);
for(int space = 0; space < remainingSpaces; space++) sb.append(" ");
res.add(sb.toString());
}
else {
int index = 0;
int totalSpaces = maxWidth - widthWithoutSpace;
int spaces = totalSpaces / (fitting - 1);
int remainingSpaces = totalSpaces % (fitting - 1);
StringBuilder sb = new StringBuilder();
while(index < fitting) {
sb.append(words[start + index]);
if(index < fitting - 1) {
for(int s = 0; s < spaces; s++) sb.append(" ");
if(remainingSpaces-- > 0) sb.append(" ");
}
index++;
}
res.add(sb.toString());
}
}
}
O(N) Where
N is total number of characters in words input string array
O(N) Where
N is total number of characters in words input string array