Skip to content

Instantly share code, notes, and snippets.

@wayetan
Created March 5, 2014 08:42
Show Gist options
  • Save wayetan/9363486 to your computer and use it in GitHub Desktop.
Save wayetan/9363486 to your computer and use it in GitHub Desktop.
Text Justification
/**
* 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,
* words: ["This", "is", "an", "example", "of", "text", "justification."]
* L: 16.
* Return the formatted lines as:
* [
"This is an",
"example of text",
"justification. "
]
* Note: Each word is guaranteed not to exceed L in length.
* 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.
*/
public class Solution {
public ArrayList<String> fullJustify(String[] words, int L) {
int wordsCount = words.length;
ArrayList<String> res = new ArrayList<String>();
int curLen = 0;
int lastI = 0;
for(int i = 0; i <= wordsCount; i++) {
if(i == wordsCount || curLen + words[i].length() + i - lastI > L) {
StringBuffer buf = new StringBuffer();
int spaceCount = L - curLen;
int spaceSlots = i - lastI - 1;
if (spaceSlots == 0 || i == wordsCount) {
for (int j = lastI; j < i; j++) {
buf.append(words[j]);
if (j != i - 1) {
appendSpace(buf, 1);
}
}
// append spaces at the end of line.
appendSpace(buf, L - buf.length());
} else {
int spaceEach = spaceCount / spaceSlots;
int spaceExtra = spaceCount % spaceSlots;
for(int j = lastI; j < i; j++) {
buf.append(words[j]);
if(j != i - 1)
appendSpace(buf, spaceEach + (j - lastI < spaceExtra ? 1 : 0));
}
}
res.add(buf.toString());
lastI = i;
curLen = 0;
}
if (i < wordsCount)
curLen += words[i].length();
}
return res;
}
private void appendSpace(StringBuffer sb, int count) {
for(int i = 0; i < count; i++) {
sb.append(' ');
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment