package pers.vic.basics.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @description:  68. 文本左右对齐 {@literal https://leetcode-cn.com/problems/text-justification/}
 * @author Vic.xu
 * @date: 2020/12/30 0030 10:41
 */
public class J0068_H_FullJustify {
    /*
    给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
    你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
    要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
    文本的最后一行应为左对齐，且单词之间不插入额外的空格。
    说明
    单词是指由非空格字符组成的字符序列。
    每个单词的长度大于 0，小于等于 maxWidth。
    输入单词数组 words 至少包含一个单词。
     */

    /**
     * 又臭又长的一道题目，感觉没什么意义
     * @param words
     * @param maxWidth
     * @return
     */
    public static List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();

       List<String> temp = new ArrayList<>();
       //当前行的字符的总长度
        int curLen = 0;
        //当前行的空格字符的长度
        int curSpace= 0;
        for (int i = 0; i < words.length; i++) {
            String cur = words[i];
            int len =  cur.length() + curLen  +curSpace;
            if (len > maxWidth) {
                result.add(generateRow(temp, maxWidth, curLen, false));
                temp.clear();
                curLen = 0;
                curSpace= 0;
            }
            temp.add(words[i]);
            curLen += cur.length();
            curSpace++;
        }
        if (!temp.isEmpty()) {
            result.add(generateRow(temp, maxWidth, curLen, true));
        }

        return result;
    }

    private static String generateRow(List<String> temp, int maxWidth, int curLen, boolean lastRow) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < maxWidth; i++) {
            sb.append(" ");
        }
        //文本的最后一行应为左对齐，且单词之间不插入额外的空格。
        if (lastRow) {
            int start = 0;
            for (String s : temp) {
                sb.replace(start, start + s.length(), s);
                start += s.length() + 1;
            }
            return sb.toString();
        }
        //间隔的空格数
        int increase = 1 ;
        //平均间隔后剩余的空格数
        int remainder = 1;
        if (temp.size() > 1) {
            increase = (maxWidth - curLen) / (temp.size() -1);
            remainder = (maxWidth - curLen) % (temp.size() -1);
        }
        int start = 0;
        for (int i = 0; i < temp.size(); i++) {
            String s = temp.get(i);
            sb.replace(start, start+ s.length(),s);
            start += s.length() + increase;
            if (remainder > 0) {
                start++;
                remainder--;
            }
        }
        return sb.toString();
    }



    public static void main(String[] args) {
        String[] words = {"This", "is", "an", "example", "of", "text", "justification."};
        String[] words2 = {"What","must","be","acknowledgment","shall","be"};
        List<String> list = fullJustify(words2, 16);
        list.forEach(s->{
            System.out.println("[" + s + "]");
        });
        String[] words3 = {"Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"};
        fullJustify(words3, 20).forEach(s->{
            System.out.println("[" + s + "]");
        });;


    }
}