Question

Formatted question description: https://leetcode.ca/all/68.html

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.

Algorithm

Use the greedy approach. Maintain a line of words and each time try to add a new word followed by a space. If adding a new word (without adding another space) will cause the total width to exceed maxWidth, then the new word can’t be added to the current line, so do text justification for the current line, add the jusitified current line to the result list, and add the new word followed by a space in a new line.

When do justification, first remove the last space in the line, and then calculate the number of spaces to be added between each pair of words. Calculate the remaining spaces and the remaining splits, where the remaining splits equals the number of words in the line minus 1. For each split from right to left, the number of spaces to be added equals the remaining spaces divided by the remaining splits (use integer division). Add the spaces and update the remaining spaces and the remaining splits. Do the process until the remaining spaces becomes 0.

For the last line, remove the last space in the line, and append spaces at the end until the last line’s width equals maxWidth.

Finally, return the result list.

Code

Java

public class Text_Justification {

    public static void main(String[] args) {

        Text_Justification out = new Text_Justification();
        Solution one = out.new Solution();


        System.out.println(one.fullJustify(new String[]{"This", "is", "an", "example", "of", "text", "justification."}, 16));
        System.out.println(one.fullJustify(new String[]{"a", "b", "c", "d", "e"}, 1));
        System.out.println(one.fullJustify(new String[]{"a", "b", "c", "d", "e"}, 3));

    }

    public class Solution {
        public List<String> fullJustify(String[] words, int maxWidth) {
            int left = 0; List<String> result = new ArrayList<>();

            while (left < words.length) {
                int right = findRight(left, words, maxWidth);
                result.add(justify(left, right, words, maxWidth));
                left = right + 1;
            }

            return result;
        }

        private int findRight(int left, String[] words, int maxWidth) {
            int right = left;
            int sum = words[right++].length();

            while (right < words.length && (sum + 1 + words[right].length()) <= maxWidth)
                sum += 1 + words[right++].length();

            return right - 1;
        }

        private String justify(int left, int right, String[] words, int maxWidth) {
            if (right - left == 0) return padResult(words[left], maxWidth);

            boolean isLastLine = right == words.length - 1;
            int numSpaces = right - left;
            int totalSpace = maxWidth - wordsLength(left, right, words);

            String space = isLastLine ? " " : blank(totalSpace / numSpaces);
            int remainder = isLastLine ? 0 : totalSpace % numSpaces;

            StringBuilder result = new StringBuilder();
            for (int i = left; i <= right; i++)
                result.append(words[i])
                    .append(space)
                    .append(remainder-- > 0 ? " " : "");

            return padResult(result.toString().trim(), maxWidth);
        }

        private int wordsLength(int left, int right, String[] words) {
            int wordsLength = 0;
            for (int i = left; i <= right; i++) wordsLength += words[i].length();
            return wordsLength;
        }

        private String padResult(String result, int maxWidth) {
            return result + blank(maxWidth - result.length());
        }

        private String blank(int length) {
            return new String(new char[length]).replace('\0', ' ');
        }

    }

All Problems

All Solutions