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 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个字符放置，不够的在中间补空格，如果空格不对等，左边的空格要多于右边的，最后一行进行左对齐。
这道题没有什么算法上的难度，主要是要考虑各种情况，所以会导致最后结果很麻烦。

• 非最后一行，判断至多能放几个单词加n-1个空格，保证空格尽量放前面，计算有几个多余的空格extraSpace，每个间隔再多放extraSpace/spaceNum个，前extraSpace%spaceNum个间隔再多放个空格。
• 最后一行单词和中间空格放好了，再在后面补够空格就行了。

代码实现

public ArrayList<String> fullJustify(String[] words, int L) {
        int i = 0;
        ArrayList<String> result = new ArrayList<>();
        while (i < words.length) {
            int j = i + 1;
            int len = words[i].length();
            while (j < words.length && len + 1 + words[j].length() <= L) {
                len = len + words[j].length() + 1;
                j++;
            }
            StringBuilder str = new StringBuilder();
            str.append(words[i]);
            if (j == words.length) {
                for (int k = i + 1; k < words.length; k++) {
                    str.append(" ");
                    str.append(words[k]);
                }
                while (str.length() < L) {
                    str.append(" ");
                }
            } else {
                int extraSpace = L - len;
                int spaceNum = j - i - 1;
                if (spaceNum == 0) {
                    while (str.length() < L) {
                        str.append(" ");
                    }
                } else {
                    for (int k = i + 1; k < j; k++) {
                        str.append(" ");
                        for (int l = 0; l < extraSpace / spaceNum; l++) {
                            str.append(" ");
                        }
                        if (k - i <= extraSpace % spaceNum) {
                            str.append(" ");
                        }
                        str.append(words[k]);
                    }
                }
            }
            result.add(str.toString());
            i = j;
        }
        return result;
    }