68. Text Justification

time: O(w*L), almot w, words nums

space: O(smaller than w)

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        if (words == null || words.length == 0) {
            return res;
        } 
        
        List<String> list = new ArrayList<>(); // single line data
        int len = 0;
        
        for (String word : words) {
            if (list.isEmpty() || len + list.size() + word.length() <= maxWidth) { // keep adding to this line 
                list.add(word);
                len += word.length();
            } else { // over single line limit, add data to res
                
                StringBuilder sb = new StringBuilder();
                int spaceCnt = maxWidth - len;
                int intervals = list.size() - 1;
                
                if (intervals == 0) { // means single word in a line
                    sb.append(list.get(0));
                    for (int i = 0; i < spaceCnt; i++) {
                        sb.append(" ");
                    }
                } else {
                    int extraSpace = spaceCnt % intervals; // ex: 10%3 = 1
                    int eachIntervalSpace = spaceCnt / intervals;
                    String space = getSpace(eachIntervalSpace, new StringBuilder());
                    
                    sb.append(list.get(0));
                    for (int i = 1; i < list.size(); i++) {
                        sb.append(space);
                        if (extraSpace != 0) {
                            sb.append(" ");
                            extraSpace--;
                        }
                        sb.append(list.get(i));
                    }
                }
                
                res.add(sb.toString());
                len = word.length();
                list = new ArrayList<>();
                list.add(word);
            }
        }
        
        //last line
        StringBuilder sb = new StringBuilder();
        sb.append(list.get(0));
        for (int i = 1; i < list.size();i++) {
            sb.append(" ");
            sb.append(list.get(i));
        }
        int leftSpace = maxWidth - sb.length();
        getSpace(leftSpace, sb);
        
        res.add(sb.toString());
        
        return res;
    }
    
    private String getSpace(int eachIntervalSpace, StringBuilder sb) {
        for (int i = 0; i < eachIntervalSpace; i++) {
            sb.append(" ");
        }
        return sb.toString();
    }
}

readable version

T: O(w*(n+s)), w is words array size, n is list data size, s is space cnt

S: O(maxWidth* rows)

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        List<String> list = new ArrayList<>();
        int len = 0;
        
        for (String word : words) {
            
            // notice here: &&
            // 當 list 有資料 且超出 maxWidth時, 把 line string 加入到 res, 把 list, len 重新初始
            if (list.size() != 0 && (len + list.size() + word.length()) > maxWidth) {
                
                String lineStr = getLineStr(list, len, maxWidth); // 做出 line string
                res.add(lineStr);
                list = new ArrayList<>();
                len = 0; 
            }
            // 加 word 到 list, len長度
            list.add(word);
            len += word.length();
        }

				// last line 做出來
        String lastStr = getLastLineStr(list, len, maxWidth);
        res.add(lastStr);
        return res;
    }
    
    private String getLineStr(List<String> list, int len, int maxWidth) {
        // add to sb   
        StringBuilder sb = new StringBuilder();
         
        int interval = list.size()-1;
        int spaceCnt = maxWidth - len;
        
        // single word case
        if (interval == 0) { // list.size() == 1
            sb.append(list.get(0));
            sb.append(" ".repeat(spaceCnt));
        } else { // multi word case
            int eachSpaceCnt = spaceCnt/interval;
            int extraSpaceCnt = spaceCnt%interval;
            String spaceStr = " ".repeat(eachSpaceCnt); // 

            sb.append(list.get(0));
            for (int i = 1; i < list.size(); i++) {
                sb.append(spaceStr);
                if (extraSpaceCnt > 0) {
                    sb.append(" ");
                    extraSpaceCnt--;
                }
                sb.append(list.get(i));
            }
        }
        return sb.toString();               
    }
    
    private String getLastLineStr(List<String> list, int len, int maxWidth) {
        StringBuilder last = new StringBuilder();
        last.append(list.get(0));
        for (int i = 1; i < list.size(); i++) {
            last.append(" ");
            last.append(list.get(i));
        }
        
        // notice here: maxWidth - sb.length()
        String remainSpaceStr = " ".repeat(maxWidth - sb.length());
        last.append(remainSpaceStr);
        return last.toString();
    }
}

/*
Extra spaces between words should be distributed as evenly as possible.

for not evenly between words, 
single space, left more space
the empty slots on the left will be assigned more spaces than the slots on the right.

last line of text, it should be left-justified, no extra space is inserted between words.

["This", "is", "an", "example", "of", "text", "justification."]

cur len 10 , if curlen + next > 16 => next line
4 + 1 +2 + 1 + 2 + | 
7

18

list res: result
two variable: list, to save words in curr line, len is words' len

for (all words) {
        // only add word to list, len
        // pre total length + all pre empty(1 space) + curr Word len <= maxWidth
        if (list isEmpty ||len + list.size() + currWord.len <= maxWidth)  // list.size() means at least  number of space
        else { // process line data, add line data to res, add word to list, len
            int interval = list.size() -1;
            int spaceCnt = maxWidth - len / interval;
            int extraSpaceCnt = (maxWidth - len) & interval
            
            String space = ...
            
            String sb = ""
            sb.append(list[0])
            for (list from 1)
                sb.append(space)

                sb.append(" ")
                extraSpaceCnt--

                sb.append(list)
            
            
        }
        res.add(sb)
        list = new list
        len = 0
        list.add(word)
}

handle last line

*/

another style

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        int wordLen = 0;
        int i = 0;
        List<String> result = new ArrayList<>();
        List<String> line = new ArrayList<>();
        while (i < words.length) {
            while (i < words.length && wordLen + words[i].length() + line.size() <= maxWidth) {
                line.add(words[i]);
                wordLen += words[i].length();
                i++;
            }
            
            if (i != words.length) {
                String eachLine = getLineStr(line, maxWidth, wordLen);
                result.add(eachLine);
            } else {
                String lastLine = getLastLineStr(line, maxWidth, wordLen);
                result.add(lastLine);
            }
            line = new ArrayList<>();
            wordLen = 0;
        }

        return result;
    }
    private String getLineStr(List<String> line, int maxWidth, int wordLen) {
        int spaceCnt = line.size() - 1;
        int spaceTotalLen = maxWidth - wordLen;

        StringBuilder sb = new StringBuilder();
        if (line.size() == 1) {
            sb.append(line.get(0));
            addSpace(sb, spaceTotalLen);
            return sb.toString();
        }
        // make sure spaceCnt is not zero
        int spaceUnitLen = spaceTotalLen/spaceCnt;
        int leftSpace = spaceTotalLen%spaceCnt;

        sb.append(line.get(0));
        for (int i = 1; i < line.size(); i++) {
            addSpace(sb, spaceUnitLen);
            if (leftSpace > 0) {
                addSpace(sb, 1);
                leftSpace--;
            }
            sb.append(line.get(i));
        }
        return sb.toString();
    }
    private void addSpace(StringBuilder sb, int cnt) {
        for (int i = 0; i < cnt; i++) {
            sb.append(" ");
        }
    }
    /*
        For the last line of text, it should be left-justified, and no extra space is inserted between words.
    */
    private String getLastLineStr(List<String> line, int maxWidth, int wordLen) {
        StringBuilder sb = new StringBuilder();
        if (line.size() == 1) {
            sb.append(line.get(0));
            addSpace(sb, maxWidth - wordLen);
            return sb.toString();
        }
        sb.append(line.get(0));
        for (int i = 1; i < line.size(); i++) {
            addSpace(sb, 1);
            sb.append(line.get(i));
        }
        int leftSpace = maxWidth - wordLen - line.size() + 1; // spaceCnt  = line.size() - 1
        for (int i = 0; i < leftSpace; i++) {
            addSpace(sb, 1);
        }
        return sb.toString();
    }

}