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.

解法1：

此题不难，也没有什么考点，可能就是考察编程能力和细心程度把。
思路大体就是先找出来每一行有哪些words,然后在分布空格。
分布空格的时候要从后往前分布，保证比较均匀且较多的空格在左面。
对于最后一行的处理要注意补齐空格。
C++

Java

public class Solution {

    public List<String> fullJustify(String[] words, int maxWidth) {

        List<String> res = new ArrayList<String>();
        if (words.length == 0 || maxWidth < 0) {
            return res;
        }

        int i = 0;

        // coding skill and detail-oriented mindset
        int currentLen = 0;
        List<String> line = new ArrayList<String>();
        while (i < words.length) {
            // need to know if it is the start of a line
            if ((line.isEmpty() ) || currentLen + 1 + words[i].length() <= maxWidth)             {
                currentLen += (line.isEmpty() ? 0 : 1 ) + words[i].length();    // add a space
                line.add(words[i]);
                i++;
            } else {
                // Convert current line into a string and push into res
                res.add(justifyLine(line, maxWidth));
                line = new ArrayList<String>();
                currentLen = 0;
            }
        }

        // treat last line
        if (!line.isEmpty()) {
            String lastLine = String.join(" ", line);
            if (lastLine.length() < maxWidth) {
                int spaces = maxWidth - lastLine.length();
                for (i = 0; i < spaces; i++) {
                    lastLine += " ";
                }
            }
            res.add(lastLine);
        }
        return res;
    }

    private String justifyLine(List<String> words, int maxWidth) {
        StringBuilder builder = new StringBuilder();

        int len = 0;
        for (String s : words) {
            len += s.length();
        }

        int spaces = maxWidth - len;
        if (words.size() == 1) {
            builder.append(words.get(0));
            for (int i = 1; i <= spaces; i++) {
                builder.append(" ");
            }
        } else {
            // distribute evenly
            List<String> temp = new ArrayList<String>();
            for (int i = words.size() - 1; i > 0; i--) {
                int average = spaces / i;
                temp.add(words.get(i));
                for (int s = 0; s < average; s++) {
                    temp.add(" ");
                }
                spaces -= average;                
            }
            // append last word
            temp.add(words.get(0));
            for (int i = temp.size() - 1; i >= 0; i--) {
                builder.append(temp.get(i));
            }
        }
        return builder.toString();
    }    
}

第二遍写的

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {

        List<String> res = new ArrayList<>();
        if (words == null || words.length == 0 || maxWidth < 0) {
            return res;
        }

        int start = 0;

        int len = 0;

        for (int i = 0; i < words.length; i++) {
            if (len == 0) len += words[i].length();
            else {
                len += (1 + words[i].length());
            }

            if (len > maxWidth) {
                // means the last step is the right interval to do a justify
                res.add(justify(words, start, i - 1, maxWidth, false));
                start = i;
                len = words[i].length();
            }
        }

        res.add(justify(words, start, words.length - 1, maxWidth, true));        

        return res;
    }

    /*
        Need to concate all words between start and end
    */
    private String justify(String[] words, int start, int end, int maxWidth, boolean lastLine) {

        StringBuilder builder = new StringBuilder();
        // left justify for the single word problem
        if (start == end) {
            builder.append(words[start]);
            for (int i = words[start].length() + 1; i <= maxWidth; i++) {
                builder.append(" ");
            }
            return builder.toString();
        }

        // Calculate the number of space between words
        if (lastLine) {
            int len = 0;
            for (int i = start; i < end; i++) {
                builder.append(words[i]);
                builder.append(" ");
                len += words[i].length() + 1;
            }
            builder.append(words[end]);
            len += words[end].length();
            while (len < maxWidth) {
                builder.append(" ");
                len++;
            }
            return builder.toString();
        }

        int totalLen = 0;
        for (int i = start; i <= end; i++) {
            totalLen += words[i].length();
        }

        int n = end - start + 1;
        /*
        Start filling the words into the sequence
        */

        int totalSpaces = maxWidth - totalLen;

        Stack<String> stack = new Stack<>();
        for (int i = end; i > start; i--) {
            stack.push(words[i]);
            int spaces = totalSpaces / (i - start);
            for (int j = 0; j < spaces; j++) {
                stack.push(" ");
            }
            totalSpaces -= spaces;
        }

        stack.push(words[start]);

        while (!stack.isEmpty()) {
            builder.append(stack.pop());
        }

        return builder.toString();        
    }


}