給定一個單詞數(shù)組和一個長度 maxWidth货葬，重新排版單詞，使其成為每行恰好有 maxWidth 個字符，且左右兩端對齊的文本起宽。

你應(yīng)該使用“貪心算法”來放置給定的單詞；也就是說济榨，盡可能多地往每行中放置單詞坯沪。必要時可用空格 ' ' 填充，使得每行恰好有 maxWidth 個字符擒滑。

要求盡可能均勻分配單詞間的空格數(shù)量腐晾。如果某一行單詞間的空格不能均勻分配，則左側(cè)放置的空格數(shù)要多于右側(cè)的空格數(shù)丐一。

文本的最后一行應(yīng)為左對齊藻糖，且單詞之間不插入額外的空格。

說明:

單詞是指由非空格字符組成的字符序列库车。
每個單詞的長度大于 0巨柒，小于等于 maxWidth。
輸入單詞數(shù)組 words 至少包含一個單詞。
示例:

輸入:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
輸出:
[
"This is an",
"example of text",
"justification. "
]
示例 2:

輸入:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
輸出:
[
"What must be",
"acknowledgment ",
"shall be "
]
解釋: 注意最后一行的格式應(yīng)為 "shall be " 而不是 "shall be",
因為最后一行應(yīng)為左對齊洋满，而不是左右兩端對齊晶乔。
第二行同樣為左對齊，這是因為這行只包含一個單詞芦岂。
示例 3:

輸入:
words = ["Science","is","what","we","understand","well","enough","to","explain",
"to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
輸出:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]

java代碼：

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

        ArrayList<String> list = new ArrayList<>();

        if(words.length == 1){
            String s = addSpace(words[0], maxWidth - words[0].length());
            list.add(s);
            return list;
        }

        int index = 0;

        while (index < words.length){

            ArrayList<Integer> tempList = new ArrayList<>();
            String s = "";
            int length = 0;
            while (index < words.length){
                s = s + words[index];
                length = length + words[index].length() ;
                if(length <= maxWidth){
                    length++;
                    tempList.add(index);
                    index++;
                }else {
                    length = length - 1 - words[index].length();
                    s = s.substring(0,s.length() - words[index].length());
                    break;
                }
            }

            //最后一行
            if(index == words.length){
                String res = "";
                for(int i = 0; i < tempList.size(); i++){
                    res =res +  words[tempList.get(i)] + " ";
                }
                if(maxWidth - res.length() >= 0) {
                    res = addSpace(res, maxWidth - res.length());
                }else {
                    res = res.substring(0,res.length() - 1);
                }
                list.add(res);
                break;
            }else if(tempList.size() > 1) {
                String res = "";

                //計算空格
                int m = (maxWidth - s.length()) / (tempList.size() - 1);
                int n = (maxWidth - s.length()) % (tempList.size() - 1);
                for(int i = 0; i < tempList.size(); i++){
                    res = res + words[tempList.get(i)];
                    if(i == tempList.size() - 1){
                        res = addSpace(res,0);
                    }else {
                        if(n > 0) {
                            res = addSpace(res, m+1);
                            n--;
                        }else {
                            res = addSpace(res,m);
                        }
                    }
                }
                list.add(res);
            }else if(tempList.size() == 1){
                String res = s;
                res = addSpace(res,maxWidth - s.length());
                list.add(res);
            }
        }

        return list;

    }


    public String addSpace(String word,int num){
        String res = word;
        for(int i = 0; i < num; i++){
            res = res + " ";
        }
        return res;
    }
}