# 0068. Text Justification
###### tags: `Leetcode` `Hard` `String`
Link: https://leetcode.com/problems/text-justification/description/
## 思路
这题不难就是比较麻烦
我们首先要算出每行结尾的单词
然后算出每一行有哪些单词之后 再把它放到一行里
放的时候有很多条件需要考虑
1. 如果这一行只有一个单词或者这是最后一行 那就要左对齐 并且单词之间的空格数为1
2. 其他情况就要平均分配空格 并且保证末尾不是空格
## Code

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        int left = 0, right = 0, n = words.length;
        List<String> ans = new ArrayList<>();
        while(left<n){
            right = findRight(words, left, maxWidth);
            ans.add(printLine(left, right, words, maxWidth));
            left = right+1;
        }
        return ans;
    }
    private int findRight(String[] words, int left, int maxWidth){
        int idx = left;
        int currLen = 0;
        int right = left;
        while(idx<words.length){
            currLen += words[idx].length();
            if(currLen<=maxWidth) right = idx;
            else break;
            currLen += 1;
            idx++;
        }
        return right;
    }
    private String printLine(int left, int right, String[] words, int maxWidth){
        int n = right-left+1;
        int blank = maxWidth;
        StringBuilder sb = new StringBuilder();
        for(int i=left; i<=right; i++) blank -= words[i].length();
        if(n==1||right==words.length-1){
            for(int i=left; i<=right; i++){
                sb.append(words[i]);
                if(i!=right){
                    sb.append(" ");
                    blank--;
                }
                else sb.append(" ".repeat(blank));
            }
        }
        else{
            int each = blank/(n-1);
            int remain = blank%(n-1);
            for(int i=left; i<=right; i++){
                if(i==right){
                    sb.append(words[i]);
                }
                else{
                    sb.append(words[i]+" ".repeat(each));
                    if(i-left<remain) sb.append(" ");
                }
            }
        }
        return sb.toString();
    }
}