68. Text Justification 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> lineList = new ArrayList<>();

        List<String> cacheList = new ArrayList<>();
        int width = 0;

        for (String word : words) {
            if (cacheList.isEmpty()) {
                cacheList.add(word);
                width += word.length();
            } else {
                if (width + 1 + word.length() <= maxWidth) {
                    cacheList.add(' ' + word);
                    width += 1 + word.length();
                } else {
                    // 放不下了，此时对当前行填充空格至 maxWidth 并加入 lineList
                    int extraSpace = maxWidth - width;
                    StringBuilder lineBuilder = new StringBuilder(maxWidth);

                    if (cacheList.size() == 1) {
                        // 该行只有一个单词，多余的空格全部添加至行尾
                        lineBuilder.append(cacheList.get(0));
                        appendSpaceToBuilder(lineBuilder, extraSpace);
                    } else {
                        // 当前行存在多个单词，需要平分多余的空格，对于不能平分的部分，累加至最左侧
                        int intervalCount = cacheList.size() - 1;
                        int intervalSpace = extraSpace / intervalCount;
                        int leftIntervalSpace = extraSpace % intervalCount;
                        lineBuilder.append(cacheList.get(0));

                        for (int i = 1; i < cacheList.size(); i++) {
                            appendSpaceToBuilder(lineBuilder, intervalSpace);
                            appendSpaceToBuilder(lineBuilder, leftIntervalSpace-- > 0 ? 1 : 0);
                            lineBuilder.append(cacheList.get(i));
                        }
                    }

                    lineList.add(lineBuilder.toString());

                    width = 0;
                    cacheList.clear();
                    cacheList.add(word);
                    width += word.length();
                }
            }
        }

        StringBuilder lastLineBuilder = new StringBuilder(maxWidth);
        for (String cache : cacheList) {
            lastLineBuilder.append(cache);
        }
        appendSpaceToBuilder(lastLineBuilder, maxWidth - lastLineBuilder.length());
        lineList.add(lastLineBuilder.toString());

        return lineList;
    }

    private void appendSpaceToBuilder(StringBuilder sb, int n) {
        for (int i = 0; i < n; i++) {
            sb.append(' ');
        }
    }
}

注意题目中提到的要尽可能均匀地分配单词间的空格数量，不能将无法平均分配的空格全部追加在第一个单词后面。

References

68. Text Justification