leetcode — text-justification

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

/**

 *

 * Source : https://oj.leetcode.com/problems/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.

 */

public class TextJustification {

    /**

     * 格式化给定的单词串，每行长度固定

     *

     * @param words

     * @return

     */

    public String[] justify (String[] words, int length) {

        if (words.length < 1) {

            return words;

        }

        if (words.length == 1) {

            words[0] = words[0] + getSpace(length - words[0].length());

            return words;

        }

        int gap = 0;

        int lineLength = words[0].length();

        List<String> result = new ArrayList<String>();

        List<String> lineWords = new ArrayList<String>(){{add(words[0]);}};

        int index = 1;

        while (index < words.length) {

            int sum = gap + lineLength + words[index].length();

            if (sum >= length) {

                result.add(buildLine(lineWords, gap, length - gap - lineLength));

                gap = -1;

                lineLength = 0;

                lineWords.clear();

            }

            gap++;

            lineLength += words[index].length();

            lineWords.add(words[index]);

            index ++;

            // 最后一行

            if (index == words.length) {

                result.add(buildLine(lineWords, gap, length - gap - lineLength));

            }

        }

        return result.toArray(new String[result.size()]);

    }

    private String buildLine (List<String> words, int gap, int remain) {

        if (words.size() == 1) {

            return words.get(0) + getSpace(remain);

        }

        StringBuilder result = new StringBuilder();

        for (int i = 0; i < words.size() - 1; i++) {

            int spaceLen = 1 + remain / gap;

            if (i < remain % gap) {

                spaceLen ++;

            }

            result.append(words.get(i) + getSpace(spaceLen));

        }

        result.append(words.get(words.size()-1));

        return result.toString();

    }

    private String getSpace (int n) {

        String space = "";

        for (int i = 0; i < n; i++) {

            space += " ";

        }

        return space;

    }

    public static void main(String[] args) {

        TextJustification textJustification = new TextJustification();

        String[] words = new String[]{"This", "is", "an", "example", "of", "text", "justification."};

        System.out.println(Arrays.toString(textJustification.justify(words, 16)));

    }

}
巴特西

leetcode — text-justification

最新文章

热门文章
