Text Justification

Posted on | Edited on | In | | Views:

68. Text Justification

Given an array of words and a width maxWidth, format the text such that each line as exactly maxWidth characters and is fully (left and right) justified.

题目的意思是, 给一个数组, 数组里面有$n$个单词, 把这些单词按照maxWidth行存放. 每一行的两端要对齐.
需要注意的是

  1. 单词的顺序不能改变
  2. 如果一行之后一个单词, 那么这个单词要左对齐
  3. 如果空格不能均匀分布在所有间隔当中, 则左边的空格需要比右边的空格多
  4. 每行要尽可能多的放单词

思路

其实这类型的题目没有什么精巧的算法可以做. 它的难点在于, 要处理的corner case太多, 比较繁琐. 对于这道题目, 几个需要解决的地方如下:

  1. 一行要放多少单词?

    • 每一行单词的总长度加上最少空格数量应当小于等于maxWidth

  2. 知道每一行的单词数量空格需要怎么分配?

    • 每一行的空格数量是maxWidth减去该行单词的总长度
    • 每一行可以填空格的地方是单词数量-1
    • 多余的空格优先添加到左边单词的间隔当中

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def fullJustify(words, maxWidth):
    start = end = 0
    res, curLen = list(), 0
    for i, word in enumerate(words):
        if len(word) + curLen + end - start > maxWidth:
            if end - start == 1:
                res.append(words[start] + ' ' * (maxWidth - curLen))
            else:
                total_space = maxWidth - curLen
                space, extra = divmod(total_space, end - start - 1)
                for j in range(extra):
                    words[start + j] = ' '
                res.append((' ' * space).join(words[start:end]))
            curLen = 0
            start = end = i
        end += 1
        curLen += len(word)
    res.append(' '.join(words[start:end]) + ' ' * (maxWidth - curLen - (end - start - 1)))
    return res

EOF