68. 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.

Solution:

We keep a last variable to store the first index we can use in a line.

We use count to store the total length of words (no space).

If count plus one more word and spaces exceed maxWidth, we know we have to use this count.

To evenly distributed spaces, we use (maxWidth - count) / (number of words in this line) as space between two words. The extra space is (maxWidth - count) % (number of words in this line).

We also need to consider when a word is the last in this line, we do not have spaces after it.

A corner case is to deal with the last line, where we fill spaces after the last word.

A annotated and clear version of code can be found HERE.



Code:

public class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        if (words == null || words.length == 0) {
            return result;
        }
        int last = 0;
        int count = 0;
        for (int i = 0; i < words.length; i++) {
            // words[i] cannot fit this line.
            // We can only put from words[last] to words[i - 1].
            if (count + words[i].length() + (i - last) > maxWidth) {
                int space = 0;
                int extra = 0;
                // We have i - last words in this line.
                // So we have i - last - 1 intervals.
                if (i - last - 1 > 0) {
                    space = (maxWidth - count) / (i - last - 1);
                    extra = (maxWidth - count) % (i - last - 1);
                }
                StringBuilder sb = new StringBuilder();
                for (int j = last; j < i; j++) {
                    sb.append(words[j]);
                    // There is no space after the last word in this line.
                    if (j == i - 1) {
                        break;
                    }
                    for (int k = 0; k < space; k++) {
                        sb.append(" ");
                    }
                    if (extra > 0) {
                        sb.append(" ");
                        extra--;
                    }
                }
                // If this line has not filled, fill trailing spaces.
                while (sb.length() < maxWidth) {
                    sb.append(" ");
                }
                result.add(sb.toString());
                count = 0;
                last = i;
            }
            count += words[i].length();
        }
        // To deal with the last line
        StringBuilder sb = new StringBuilder();
        for (int i = last; i < words.length; i++) {
            sb.append(words[i]);
            if (sb.length() < maxWidth) {
                sb.append(" ");
            }
        }
        while (sb.length() < maxWidth) {
            sb.append(" ");
        }
        result.add(sb.toString());
        return result;
    }
}