Text Justification in Java
August 15, 2014
This is a problem on LeetCode and the submission rate, as of August 2014, is 14% where of the 56,868 submissions only 7,954 were right. As you can see, this problem is a bit daunting. The trick is the math operators and when to use them. There’s many solutions to this but, for me, in Java, here’s a fun way to solve that.
The Problem
Given an array of words and a length L, format the text such that each line has exactly L 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 L 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.
For example, take this array: ["This", "is", "an", "example", "of", "text", "justification."], and we’ll want 16 characters in length.
Return the formatted lines as:
[
"This is an",
"example of text",
"justification. "
]Note: Each word is guaranteed not to exceed the length – which is 16 in this case.
Corner Cases: A line other than the last line might contain only one word. What should you do in this case? In this case, that line should be left-justified.
My Approach
What’s the best approach here? Iterative is the approach as the input can be many lines and the length can be as long as 50 to 100. If we keep doing a recursive approach, eventually, we’d get a stackoverflow if we handle too many lines for processing. Keep in mind the processing time for all of this.
So, first I create three ListArray. One to return, one to copy the String[] words, and one to use the words to use during the line justification.
So then we check if the word length fits exactly into the L and from there, we simply add that there. If not (which usually it isn’t), we do a loop until a word fits and then check for the upcoming space. Usually the word fits with an upcoming space.
So, if the word doesn’t fit the length, we cut it off there and continue with the justification. If the word fits with an upcoming space, we continue because we can assume another word is allowed to fit.
We continue this process until 1 of 2 things happen:
- We run out of characters to process in the line (smooth fit = # of words and one space in between)
- The word length is longer than “characters left”
Usually, we hit number 2 and then we begin the line justification. If number 1 is met, there is no need for justification because the line fits perfectly with one space between each word. However, like I said, usually #2 is met because smooth fits are rare.
Before we move onto the function to justify the line, we check to see if there are any words left in the ListArray which has all of the words. If there are no words left, that signifies that we are on the last line and no text justification is needed other than a simple left justification.
In that case, all you do is add the words like you would as a regular append function would. Then take the remaining length of the spaces left and add the spaces to the line to meet the L requirement.
If not, we take the function and this is where the beauty happens. We use a StringBuilder because StringBuilder is faster when performing concatenations. This is because when you concatenate a String, you are internally creating a new object every time since String is immutable (unable to be changed).
So, in the function createLine, we get the string of words to justify, length of words of words, the length to use and if it’s the last line. If it is the last line, we do simply a left justify (which I explained before), if not we keep going.
So when we keep going, we take the spaces by doing length of words combined minus length of the line (L). We take the number of spaces divided by the words total to get the number of spaces each word gets in between (even). Then we take the same variables (spaces/words total) and do the remainder math operator (%) to get the remaining left.
The first loop adds the word to the StringBuilder and the next for loop adds the spaces each word gets. Finally, to achieve justification, we go through the remainder and add one space until the remainder is less than the words to add.
What happens is that the justification goes from left to right (because English is read left to right) so place the odd spaces starting from the left. We add one from the remainder (of the decimal that was “each word gets x amount of spaces) until we are done.
Once we are done, your line should be justified but to make sure, we cut the line to the length given, using setLength, to remove any trailing spaces and then return the StringBuilder.
Once returned, the function ends and we parse the StringBuilder to a String (.toString()) and add it to the list to return. We clear the toUse list and set the wordsUsed to 0 and get it ready for the next iteration.
We do this until we have no more words left in wordsLeft and after that, we will have a list full of justified lines ready to send back.
My Solution
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class main {
public static void main(String[] args) {
String[] theText = {"This", "is", "an", "example", "of", "text", "justification."}; // 18
//String[] theText = {"What","must","be","shall","be."}; // 12
//String[] theText = {"Listen","to","many,","speak","to","a","few."}; // 6
int L = 18;
System.out.println(main.fullJustify(theText, L));
}
public static List<String> fullJustify(String[] words, int L) {
// First we create the list to send back
List<String> list = new ArrayList<String>(); // make a list every row
// Then we create two more. wordsLeft = words left to use
List<String> wordsLeft = new ArrayList<String>(Arrays.asList(words)); // words left to recover from
// and the words to use in a current line
List<String> toUse = new ArrayList<String>();
// words used so loop knows how many words are left.
int wordsUsed = 0;
// used to detect if on last line
boolean lastLine = false;
// if we receive a list with no words... we output the number of spaces
// as defined by L so L = 3 would output [ ]
if (wordsLeft.get(0).length() == 0) {
// new string buffer to add the word
StringBuffer noBuffer = new StringBuffer(L);
// add spaces as dictated by L
for (int addGhostSpaces = 0; addGhostSpaces < L; addGhostSpaces++)
noBuffer.append(" ");
list.add(noBuffer.toString());
return list;
} else{
// Normally, we do not so we do this instead.
// Go through words left list while
// there is still words in it
while (wordsLeft.size() > 0) {
// These variables help set the spaces, word index
// and character values left to be analyzed
int lengthTotalChars = 0;
int spacesLeft = L;
int charsTotal = 0;
int i = 0;
// while we have spaces left, and
// words used is MORE than the size of wordsLeft
while (spacesLeft > 0 && wordsUsed < wordsLeft.size()) {
// words length to detect if there's space
// to fit into the L of the paragraph
int getWordLength = wordsLeft.get(i).length();
// To avoid negative numbers, if spaces left
// is more than word length, that means no
// room left so we sit it to 0
if (spacesLeft < getWordLength) spacesLeft = 0;
// if space left is EQUAL to word length (smooth fit)
// OR space left is MORE than word left (above it)
// there is still room so we advance.
if (spacesLeft >= getWordLength) {
// take space away from length of word
// for every character, add to characters total
// add to the ListArray called toUse for parsing
// lastly, take away wordsToGo and add one to wordsUsed
spacesLeft -= getWordLength;
charsTotal += wordsLeft.get(i).length();
toUse.add(wordsLeft.get(i));
wordsUsed++;
// if length of total chars (word length & space)
// is LESS than length, we can continue adding
// to the variables
if (lengthTotalChars < L) {
lengthTotalChars++;
spacesLeft--;
}
}
// we move onto the next
// word so we +1 (i) the number
i++;
}
// we take the number of words left
// and clear it from 0 tp that.
wordsLeft.subList(0, toUse.size()).clear();
// if we have no more words left, obviously
// that means we are on the last line
if (wordsLeft.size() == 0) lastLine = true;
// we now parse the line accordingly
// and return the new justified string to add to List
// toUse = words fitted in one line, L = length of paragraph
// charsTotal = number of characters (excluding spaces)
// lastLine == detect if on last line)
list.add(createLine(toUse, L, charsTotal, lastLine).toString());
// we clear the toUse list after
// every line is finished
// and set the wordsUsed to 0.
toUse.clear();
wordsUsed = 0;
}
// after every word is finished parsing
// we return the new list
return list;
}
}
public static StringBuffer createLine(List<String> s, int lineLength, int charsTotal, boolean lastLine) {
// create a new StringBuffer for performance
// during string concatenation
StringBuffer sb = new StringBuffer(lineLength);
// Set the length of paragraph
int spaceInAll = lineLength;
// set words total to use
int wordsTotal = s.size();
// if we're on the last line,
// we are going to left-justify instead
if (lastLine) {
for (int spaceLoop = 0; spaceLoop < s.size(); spaceLoop++) {
// add append the string with the word and extra space
sb.append(s.get(spaceLoop) + " ");
int newWordLength = s.get(spaceLoop).length() + 1;
spaceInAll -= newWordLength;
}
// what remains gets appended with more spaces
// until we run out of spaces
for (int remainingLastSpace = 0; remainingLastSpace < spaceInAll; remainingLastSpace++)
sb.append(" ");
}else{
// If not last line, we'll check if the whole
// word takes up the whole line
if (s.get(0).length() == lineLength) {
// so we just append the word
// without adding more spaces
sb.append(s.get(0));
}else{
// here's where the MAGIC happens
// spaces is the paragraph divided by characters total
int spaces = lineLength - charsTotal;
// lastToAdd = will say how many
// words to use in the algorithm
int lastToAdd;
if (wordsTotal == 1) {
// if we have 1 word
// lastToAdd will obviously be 1
lastToAdd = wordsTotal;
} else {
// if not, it will be word total MINUS 1
lastToAdd = wordsTotal-1;
}
// number = get spaces divide by words
// This is how many space breaks are in line
int number = spaces/lastToAdd;
// get the remaining (if odd space breaks)
// to add to the left-most for that "justification"
// example "Hello World!"
// L=14 -----XXY------ [X = number, Y =toAdd_remain]
int toAdd_remain = spaces%lastToAdd;
// every word, we iterate this loop
for (int remainder = 0; remainder < wordsTotal; remainder++) {
// first we add the word to the StringBuffer
sb.append(s.get(remainder));
// each word gets this mount of spaces
for (int sP = 0; sP < number; sP++)
sb.append(" ");
// if the loop is less than toAdd_remainder
// that means we still have one more space
// to give to this word on the line
if (remainder < toAdd_remain) sb.append(" ");
}
}
}
// Then we trim the sentence to the length
// by trimming the trailing added space
// so it fits exactly into the paragraph line
sb.setLength(lineLength);
// Readability for the console
System.out.println(sb.toString() + "| (" + sb.toString().length() + ")");
// we return the newly-justified
// StringBuffer and we are finished
// with the space parsing
return sb;
}
}Despite this being from 2014, I am posting this again on my new blog in 2017. Excuse any of my anti-design patterns in Java. :-)