Text Justification

Text Justification

• 没有太多的算法，就是考察各种edge case

• 需要考虑全面各种情况

• 如果是普通的line，则需要full justify

• 如果是 lastLine, 则需要left justify, 并且每一个word直接只能有one space

• 这题为了写出clean code还可以多写sub method

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        int n = words.length;
        int start = 0;
        while (start < n) {
            int end = findEnd(words, start, maxWidth);
            res.add(justify(words, start, end, maxWidth));
            start = end + 1;
        }
        return res;
    }
    
    private int findEnd(String[] words, int start, int maxWidth) {
        int n = words.length;
        int end = start, width = words[end++].length();
        while (end < n && width + 1 + words[end].length() <= maxWidth) {
            width += words[end].length() + 1;
            end++;
        }
        return end - 1;
    }
    private String justify(String[] words, int start, int end, int maxWidth) {
        if (start == end) {
            return padRight(words[start], maxWidth);
        }
        boolean lastLine = end == words.length - 1;
        int width = 0;
        for (int i = start; i <= end; i++) {
            width += words[i].length();
        }
        int gap = end - start;
        int spaceBetween = lastLine ? 1 : (maxWidth - width) /gap;
        int remainder = lastLine ? 0 : (maxWidth - width) % gap;
        StringBuilder sb = new StringBuilder();
        for (int i = start; i < end; i++) {
            sb.append(words[i]);
            sb.append(whitespace(spaceBetween));
            sb.append(remainder-- > 0 ? " " : "");
        }
        sb.append(words[end]);
        if (lastLine) {
            return padRight(sb.toString(), maxWidth);
        } else {
            return sb.toString();
        }
    }
    
    private String padRight(String str, int maxWidth) {
        return str + whitespace(maxWidth - str.length());
    }
    
    private String whitespace(int cnt) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < cnt; i++) {
            sb.append(" ");
        }
        return sb.toString();
    }
}