KK's blog

每天积累多一些

0%

LeetCode 068 Text Justification

Posted on Edited on Disqus:

LeetCode



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

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

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

Note:

A word is defined as a character sequence consisting of non-space characters only. Each word’s length is guaranteed to be greater than 0 and not exceed maxWidth.
The input array words contains at least one word.

Example 1:

Input: words = [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”], maxWidth = 16
Output:
[
   “This    is    an”,
   “example  of text”,
   “justification.  “
]


Example 2:

Input: words = [“What”,”must”,”be”,”acknowledgment”,”shall”,”be”], maxWidth = 16
Output:
[
  “What   must   be”,
  “acknowledgment  “,
  “shall be        “
]
Explanation: Note that the last line is “shall be    “ instead of “shall     be”, because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified becase it contains only one word.


Example 3:

Input: words = [“Science”,”is”,”what”,”we”,”understand”,”well”,”enough”,”to”,”explain”,”to”,”a”,”computer.”,”Art”,”is”,”everything”,”else”,”we”,”do”], maxWidth = 20
Output:
[
  “Science  is  what we”,
  “understand      well”,
  “enough to explain to”,
  “a  computer.  Art is”,
  “everything  else  we”,
  “do                  “
]


Constraints: 1 <= words.length <= 300
1 <= words[i].length <= 20 words[i] consists of only English letters and symbols.
1 <= maxWidth <= 100 words[i].length <= maxWidth

题目大意：

加入尽量均等的空格使得单词组成的每行左右对齐

Round Robin加入space解题思路(推荐)：

法二是先将一个space加入到预结果，再计算extra spaces，计算比较复杂。此法与maxWidth比较时，用1个space，而最后不区分正常space和extra space，将space按round robin方法加入，不用考虑法二复杂的计算公式。

注意事项：

  1. 关键变量两个word_list, cur_len. 用目前结果cur_len + 空格个数 + 准加入单词长度与maxWidth比较。1个单词和2个单词以上的空格情况都照顾到了。
  2. i % (len(word_list) - 1)若长度为1时候，不能对0取余，所以此情况要变成1， 加入or 1。word_list中的单词加入空格
  3. 最后一行用ljust向左对齐，右边补齐空格

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
	res = []
	word_list, cur_len = [], 0
	for word in words:
		if cur_len + len(word_list) + len(word) > maxWidth:
			for i in range(maxWidth - cur_len):
				word_list[i % (len(word_list) - 1 or 1)] += ' '
			res.append(''.join(word_list))
			word_list, cur_len = [], 0
		word_list.append(word)
		cur_len += len(word)
	return res + [' '.join(word_list).ljust(maxWidth)]

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

计算extra space算法II解题思路：

用公式计算空格数和位置：

1
extra_space_num, idx = math.ceil(num_space_left / (len(buffer) - 1)), num_space_left % (len(buffer) - 1)

解题步骤：

N/A

注意事项：

0.1 题目要求： 若空格有多余，尽量分到前面；若某一行只有一个单词，左对齐右补空格；最后一行无论多少个单词都是左对齐右补空格
0.2 用buffer记录这一行的单词，count记录单词和空格的长度，若count + 当前单词长度大于maxWidth就处理

  1. 公式：extra_space_num, idx = math.ceil(num_space_left / (len(buffer) - 1)), num_space_left % (len(buffer) - 1)
    有多余空格就分配到单词间隔个数中len(buffer) - 1，而不是单词个数. 商为多余的空格个数，余数为从第几位开始，减一个空格。如x x x x，idx = 1，表示平分后仍多出一个空格，所以分配到第0个到第1个单词之间，也就是[:idx + 1]中，而剩余的buffer[idx + 1:]比上述少一个空格。它们之间的连接用较少空格数
  2. 公式中若余数为0， 表示全部平均分配，这时要取extra_space_num + 1，所以令idx = len(buffer) - 1。 extra_space_num + 1里面的1是原本就应该有一个空格，所以此情况并没有额外多空格。
  3. 公式中len(buffer) - 1可能为0，所以要特别处理，对应到题目要求的第二点
  4. 最后一行是buffer的内容，出来for循环后，向右加空格，对应到题目要求的第三点，代码与第二点要求类似

Python代码：

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
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
	# words.append(' ' * maxWidth)
	buffer, count, res = [], 0, []
	for word in words:
		new_length = len(word) if len(buffer) == 0 else 1 + len(word)
		if count + new_length <= maxWidth:
			buffer.append(word)
			count += new_length
		else:
			num_space_left = maxWidth - count # 3
			if len(buffer) > 1:
				extra_space_num, idx = math.ceil(num_space_left / (len(buffer) - 1)), num_space_left % (len(buffer) - 1) # 3, 0
				if idx == 0:
					idx = len(buffer) - 1
				tmp = (' ' * (extra_space_num + 1)).join(buffer[:idx + 1]) + (' ' * extra_space_num) #
				tmp += (' ' * extra_space_num).join(buffer[idx + 1:])
				res.append(tmp.strip())
			else:
				tmp = buffer[0] + (' ' * (maxWidth - len(buffer[0])))
				res.append(tmp)
			buffer = [word]
			count = len(word)

	if buffer:
		res.append(' '.join(buffer))
		res[-1] += (' ' * (maxWidth - len(res[-1])))
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

Free mock interview