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.

click to show corner cases.

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.

这道题没有什么算法,就是实现比较麻烦,首先L如果是0,则输出为空
然后如果是正常输入
1.首先将所有的字扫一遍,如果加起来不超过L的,在前面append空格以后加入到string中,当超过L的话,那个字加入到下一个string中,而当前string放入一个arraylist里。
2.然后将所有arraylist里是string扫一遍,从左到右,如果不达到L,那么碰到空格就加入空格,一直从左到右这样加知道size达到为止。
3.另外如果是最后一行或者是只有一个单词,那么就直接在末尾加空格知道填满L为止。

有几个要注意的地方,第二步中第一个和最后一个单词不可能是空格,所以可以不用考虑,另外就是第二步中insert了空格以后i要++才能保持原来指向的空格。

public class Solution {
    public ArrayList<String> fullJustify(String[] words, int L) {
        ArrayList<StringBuilder> res = new ArrayList<StringBuilder>();
        StringBuilder temp = new StringBuilder();
        
        //add word to array
        for (int i = 0; i < words.length; i++)
        {
            if (temp.length() == 0) // if empty, add it to string
            {
                temp.append(words[i]);
            }
            else if (temp.length() + words[i].length() + 1 <= L)
            {
                temp.append(" ");
                temp.append(words[i]);
            }
            else
            {
                res.add(temp);
                temp = new StringBuilder();
                temp.append(words[i]); // current word in the line
            }
        }
        res.add(temp);// last word in the array
        //justify
        for (int j = 0; j < res.size(); j++)
        {
            StringBuilder s = res.get(j);
            boolean oneWord = true;
            int i = 0;
            for (i = 0; i < s.length(); i++)
            {
                if (s.charAt(i) == ' ')
                {
                    oneWord = false;
                    break;
                }
            }
            if (!oneWord && j != res.size() - 1)// if not one word or last line
            {
                while(s.length() < L)
                {
                    if (s.charAt(i) == ' ' && s.charAt(i+1) != ' ') 
                    {
                        s.insert(i, ' ');
                        i++;
                    }
                    i = (i == s.length()-1)? 0: i+1; // in normal condition, last char is not " "
                }
            }
            else
            {
                while(s.length() < L)
                {
                    s.append(" ");
                }
            }
        }
        ArrayList<String> r = new ArrayList<String>();
        if (L == 0)
        {
            r.add("");
            return r;
        }
        for (StringBuilder s : res)
        {
            r.add(new String(s));
        }
        return r;
    }
}

One thing to notice is that we need to check if each line contains one word (empty string count as one word), if so we only append spaces after the word, otherwise we expend the spaces in between. Also when doing preprocessing, we delete the trailing space if exist.

public class Solution {
public ArrayList fullJustify(String[] words, int L) {
//first put all the elments into an array.
ArrayList res = new ArrayList();
ArrayList ans = new ArrayList();
if (words.length == 0)
return ans;
StringBuilder tmp = new StringBuilder();
for (int i = 0; i < words.length; i++) {
if (tmp.length() + words[i].length() <= L) {
tmp.append(words[i]);
if (tmp.length() = 1 && tmp.charAt(tmp.length() -1) == ‘ ‘)
tmp.deleteCharAt(tmp.length()-1);
res.add(tmp);
// expend spaces in each line to make sure they are justified
for (int i = 0; i < res.size(); i++) {
StringBuilder t = res.get(i);

boolean oneWord = true;
if (t.length() == 0 || t.length() == 1 || i == res.size() – 1)
oneWord = true;
else {
for (int j = 0; j < t.length(); j++) {
if (t.charAt(j) == ' ') {
oneWord = false;
break;
}
}
}
// if only one word
if (oneWord) {
while(t.length() < L)
t.append(" ");
}
else {
int index = 0;
while(t.length() 1 && t.charAt(index) != ‘ ‘ && t.charAt(index+1) == ‘ ‘) {
t.insert(index + 1, ‘ ‘);
if (t.length() == L)
break;
}
index++;
if (index == t.length() – 2) // if one iteration does not fill the length L.
index = 0;
}
}
}
for (StringBuilder sb : res) {
ans.add(new String(sb));
}
return ans;
}
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s