Sunday, December 28, 2014

Word wrap / Text Justification

Word Wrap / String Justification algorithm. 
Given a set of words and a length. 
You are required to print the words such that the words on each line end almost on the same column and the number of trailing spaces at the end is minimized. 


Given aaa bb cc ddddd and length is 5 print the following output. 



aaa 
bb cc 
ddddd

Click here for the original problem. 
This one is similar to LeetCode's Text Justification. Apparently the question is not clear, the length of each line should be 5, but there is one space after "bb" and one space after "cc", which makes the total length of that line 6. I am not sure if there should be no space between "bb" and "cc" or no space after "cc". The common sense tells me there should be one space between two strings and based on "the number of trailing spaces at the end is minimized", I go with the second way.

In case the guy who posted this problem remembers the question wrong and this should be the same as the Text Justification. I include that code as well. 

Text Justification


public class Solution {
    public ArrayList fullJustify(String[] words, int L) {
        if (words == null)
            throw new NullPointerException("Null string array!");
        ArrayList rst = new ArrayList ();
        if (words.length == 0)
            return rst;
        int maxLength = words[0].length();
        for (int i = 0; i < words.length; i++) {
            maxLength = Math.max(maxLength, words[i].length()); 
        }
        if (maxLength > L)
            return rst;
            
        int prev_start = 0;
        int currSum = 0;
        int countWord = 0;
        for (int i = 0; i <= words.length; i++) {
            if (i == words.length || (currSum + words[i].length() + countWord > L)) {
                int totalSpace = L - currSum;
                String tmp = "";
                if (i == words.length || countWord == 1) {
                    for (int j = prev_start; j < i; j++) {
                        tmp += words[j];
                        if (j != i - 1)
                            tmp += " ";
                    }
                    tmp = appendSpace(tmp, L - tmp.length());
                }
                else {
                    int spaceEachWord = totalSpace / (countWord - 1);
                    int extraSpace = totalSpace % (countWord - 1);
                    for (int j = prev_start; j < i - 1; j++) {
                        tmp += words[j];
                        if (j != i - 1) {
                            tmp = appendSpace(tmp, spaceEachWord);
                            }
                        
                        if (extraSpace > 0) {
                            tmp += " ";
                            extraSpace--;
                        }
                    }
                    tmp += words[i - 1];
                }
                rst.add(tmp);
                if (i == words.length)
                    break;
                prev_start = i;
                currSum = words[i].length();
                countWord = 1;
            }
            else {
            currSum += words[i].length();
            countWord++;
            }
        }
        return rst;
        
    }
    private String appendSpace(String s, int space) {
        String rst = s;
        for (int i = 0; i < space; i++)
            rst += " ";
        return rst;
    }
}


Word Wrap


import java.util.ArrayList;


public class TextJustification {
 public ArrayList fullJustify(String[] words, int L) {
        if (words == null)
            throw new NullPointerException("Null string array!");
        ArrayList rst = new ArrayList ();
        if (words.length == 0)
            return rst;
        int maxLength = words[0].length();
        for (int i = 0; i < words.length; i++) {
            maxLength = Math.max(maxLength, words[i].length()); 
        }
        if (maxLength > L)
            return rst;
            
        int prev_start = 0;
        int currSum = 0;
        int countWord = 0;
        for (int i = 0; i <= words.length; i++) {
            if (i == words.length || (currSum + words[i].length() + countWord > L)) {
                int totalSpace = L - currSum;
                String tmp = "";
                if (i == words.length || countWord == 1) {
                    for (int j = prev_start; j < i; j++) {
                        tmp += words[j];
                        if (j != i - 1)
                            tmp += " ";
                    }
                    tmp = appendSpace(tmp, L - tmp.length());
                }
                else {
                    int spaceEachWord = totalSpace / (countWord - 1);
                    int extraSpace = totalSpace % (countWord - 1);
                    for (int j = prev_start; j < i - 1; j++) {
                        tmp += words[j];
                        if (j != i - 1) {
                            tmp = appendSpace(tmp, spaceEachWord);
                            }
                        
                        if (extraSpace > 0) {
                            tmp += " ";
                            extraSpace--;
                        }
                    }
                    tmp += words[i - 1];
                }
                rst.add(tmp);
                if (i == words.length)
                    break;
                prev_start = i;
                currSum = words[i].length();
                countWord = 1;
            }
            else {
            currSum += words[i].length();
            countWord++;
            }
        }
        return rst;
        
    }
    private String appendSpace(String s, int space) {
        String rst = s;
        for (int i = 0; i < space; i++)
            rst += " ";
        return rst;
    }

}

No comments:

Post a Comment