LeetCode: 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 exactlyL 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.

Solution:
The idea is not difficult at all, but caution needs to be exercised when dealing with corner cases. See the code below:

	public ArrayList<String> fullJustify(String[] words, int L) {
	ArrayList<String> res = new ArrayList<String>();
	int numWords = 0;
	String str = "";
	if(L<=0 || words.length <=0){
	res.add(str);
	return res;
	}
	for(int i=0; i<words.length; i++){
	if(str.length()+ words[i].length()>L){
	//if adding current word, the length will exceed, so justify what have been collected
	res.add(justify(words, str, numWords, i, L));
	i--;
	str = "";
	numWords=0;
	}
	else if(str.length()+ words[i].length()==L){
	//if adding current word, the length will be exactly L. Add the word and a valid line
	str += words[i];
	res.add(str);
	str = "";
	numWords=0;
	}
	else{//adding a more word
	numWords++;
	if(i == words.length-1){//if current word is the last word, get the last line
	str += words[i];
	for(int j=str.length(); j<L; j++){//pad the rest with spaces
	str +=" ";
	}
	res.add(str);
	}
	else str += words[i] + " ";
	}
	}
	return res;
	}
	//note A[curIndex] is not included in this line
	public String justify(String[] words, String str, int numWords, int curIndex, int L) {
	int totalCharLen =0;
	int totalSpaceLen =0;
	int[] numSpace = new int[numWords-1];//the number of spaces is less than that of words by 1
	int aveNum = 0;
	String ret = "";
	char[] cs = new char[L];
	if(numWords == 1){//only one word in the whole line
	for(int i=0; i<L; i++){
	if(i<words[curIndex-1].length())
	cs[i] = words[curIndex-1].charAt(i);
	else
	cs[i] = ' ';
	}
	ret = String.valueOf(cs);
	return ret;
	}
	//more than one word in the line, deal with the spaces
	for(int i=1; i<=numWords; i++){
	//get the total number of characters in the line
	totalCharLen +=words[curIndex-i].length();
	}
	//get the total number of sapces in the line
	totalSpaceLen = L-totalCharLen;
	//get the average number of sapces between two words
	aveNum = totalSpaceLen/(numWords-1);
	for(int i=0; i<numWords-1; i++){
	numSpace[i] = aveNum;
	// the empty slots on the left will be assigned more spaces than the slots on the right
	if(i<totalSpaceLen%(numWords-1)) numSpace[i]++;
	}
	//pad spaces
	String spaces="";
	for(int i=1; i<=aveNum; i++) {
	spaces +=" ";
	}
	int n = numWords;
	int j=0;
	while(n>1){
	ret += words[curIndex-n];
	ret += spaces;
	if(j<(numWords-1)&&numSpace[j] >aveNum)
	ret +=" ";
	n--;
	j++;
	}
	ret += words[curIndex-1];
	return ret;
	}

view raw gistfile1.java hosted with ❤ by GitHub