从这道字符串处理的难题，寻找解决复杂问题的套路
从这道字符串处理的难题，寻找解决复杂问题的套路
今天是LeetCode专题的第39篇文章，我们一起来看下LeetCode第68题 Text Justification。
这题官方给的难度是Hard，通过率不到1/3。并且624赞同，1505反对。光看这个数据，可能会觉得这题很难，或者是藏着什么坑点，但其实做下来之后发现并不是这样的。题目只能算是稍稍复杂，并不算棘手，唯一的可能大概是大家比较畏惧字符串处理的问题吧。
题意
题目会给定一系列单词和一个每行的最长长度maxWidth，要求我们根据这个长度，将这些单词重新整理，整理得尽可能整齐。
这里整齐的定义有这么几条，首先，重新整理之后的文本的每一行的长度都是固定的，就是maxWidth。为了达成这点，题目保证单词当中不会出现长度超过这个限制的单词。
另外，要求用尽量少的行数来存放这些单词。也就是说每一行要尽可能存放尽可能多的单词，并且单词之间的顺序不能改变，也就是要按照题目给定的顺序来摆放这些单词。每一行对于单词的数量没有限制，可以是一个，也可以是多个。如果一行当中的单词数量超过1，那么需要在单词之间摆放空格。要求单词之间的空格尽可能均匀，如果不可能保证每个空隙的空格数量完全相等，那么要保证前面的空格数量大于等于后面。
文本的最后一行要求进行左对齐，也就是说单词全部靠左摆放，单词之间只有一个空格。剩余的空格全部摆放在行末。
我这样说起来感觉很麻烦的样子，但实际上很简单，我们看个样例就明白了。
输入:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
输出:
[
"What must be",
"acknowledgment ",
"shall be "
]
解释: 注意最后一行的格式应为 "shall be " 而不是 "shall be",
因为最后一行应为左对齐，而不是左右两端对齐。
第二行同样为左对齐，这是因为这行只包含一个单词。在上面这个例子当中，我们可以看到输入的单词被分成了三行，每行16单位的长度。单词之间被填充了空格，单个成行以及最后一行按照左对齐的方式摆放，也就是所有的空格都在右侧。
解法
这题的解法很明显了，就是题目的意思本身。也就是说这也是一道模拟题，那么和之前讲过的其他模拟题一样，它的特点就是题目简单，但是用代码做起来并不简单。我们想一下也很容易发现，首先，我们要把单词切分，找出哪几个单词在一行。接着这些单词的摆放又有讲究，单个的单词和多个单词的摆放方式不一样，并且还要判断是不是最后一行，因为最后一行的摆放方式也不一样。
这些问题解决了之后又面临空格的问题，我们需要合理地安排空格，使得单词摆放尽量均匀。要做到空格尽量均匀，需要先计算究竟有多少个空格又有多少个间隙。然后算出来每个间隙安排多少个空格，但是由于空格的数量并不一定能均分，所以还需要保证前面的间隙空格比后面的多一个。所以，我们又需要计算余数，算出究竟有多少个间隙空格多一个……
很显然，这个解法非常麻烦，但是一时之间好像也没有特别好的方法。如果是新手来做的话，可能会有头大如斗、心乱如麻的感觉，或者是一鼓作气写了很多代码，然后运行之后发现情况完全不对，心态崩溃。
所以在我们开始正式写代码之前，先和大家聊点心得。
之前读过这么一则小故事，说是有一个得道高僧，修行多年终于成道。之后记着去采访他，问他大师你得道了之后，生活有什么变化吗？
高僧说，没有，每天还是挑水、砍柴、做饭。
记者又问，那你成道之前的生活难道不也是这样吗？
高僧摇头，不一样，成道之前，挑水的时候想看砍柴，砍柴的时候想着做饭，做饭的时候又想着挑水。成道之后，挑水就是挑水，做饭就是做饭。
故事虽然是假的，但是道理是真的。我们每天这么多事情要做，我经常发现自己有时候一件事情刚开始做或者是刚做到一半，心里冒出其他的事情来。有的时候意志力薄弱，就被转移了注意力，去做别的事了。然后别的事情做到一半又跳回到当前的事情上来。不仅做事如此，解题的时候也是如此，有时候眼前的问题明明没有解决，满脑子装的都是以后的问题。显然，这样效率很低。
我们虽然成不了得道高僧，但也可以从故事当中得到一点启发。在列计划的时候统筹全局，高瞻远瞩。而在执行的时候就认准脚下，之后的问题之后再想。
我们把这个思路套用到解题上来，这题虽然细节很多，但是我们大体上划分一下无非也就两个主要的流程。第一个流程是切分，也就是单词的切分，哪些单词成为一行。第二个流程是填充，也就是在单词之间填充上合适的空格数量，使其符合题意。
我们怎么判断这一行究竟要包含几个单词？当然是根据单词的长度来判断，所以我们需要维护单词的总长度，还需要一个list存储当前候选成为一行的候选词。
什么情况下可以添加新的单词？显然，只有新的单词的长度加入不会超过限制的时候才可以。否则就要把这个单词放到下一行去。
所以我们根据这个思路，可以写出切分的代码：
curLen, curWords = 0, []
for w in words:
# 由于要保证单词之间至少有一个空格，所以还需要加上候选词的数量
if curLen + len(w) + len(curWords) <= maxWidth:
curLen += len(w)
curWords.append(w)
else:
# TODO: 在curWords当中填充空格
# 把单词w放入下一行中
curLen, curWords = len(w), [w]
# 最后一行单独处理
if len(curWords) > 0:
# TODO 填充最后一行这样我们切分的逻辑就写好了，很明显它和填充没有任何关联。作为一个独立的算法组件，我们可以单独测试这个部分，保证它的正确性。这样也方便之后我们写完所有代码进行整体的debug。
填充的逻辑看起来麻烦一些，但是仔细列举一下也还好，所有的变量都是可以确定的。首先需要填充的空格数量是确定的，它是maxWidth减去目前选出的单词总长。填充的空隙数量也是确定的，就是单词的数量-1。所以我们用空格数量除以空隙数量就得到了每个空隙分到的空格数。我们用空格的数量对空隙数取模，得到的就是分到空格多一个的空隙的数量。
def process(self, curLen, curWords, maxWidth):
# 空格数量
num_space = maxWidth - curLen
# 如果只有一个单词就没必要考虑分配，直接填充空格即可
if len(curWords) == 1:
return curWords[0] + ' ' * (maxWidth - curLen)
# 每个空隙分到的空格数量
num_sep = num_space // (len(curWords) - 1)
# 分到空格数量多一个的空隙
head_sep = num_space % (len(curWords) - 1)
cur = ''
# 分配
for i in range(len(curWords) - 1):
cur = cur + curWords[i] + (' ' * (num_sep + 1) if i < head_sep else ' ' * num_sep)
# 分配结束之后把最后一个单词连上
cur = cur + curWords[-1]
return cur我们把这两个组件串联在一起就是最终的代码。
class Solution:
def process(self, curLen, curWords, maxWidth):
num_space = maxWidth - curLen
if len(curWords) == 1:
return curWords[0] + ' ' * (maxWidth - curLen)
num_sep = num_space // (len(curWords) - 1)
head_sep = num_space % (len(curWords) - 1)
cur = ''
for i in range(len(curWords) - 1):
cur = cur + curWords[i] + (' ' * (num_sep + 1) if i < head_sep else ' ' * num_sep)
cur = cur + curWords[-1]
return cur
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
ret = []
curLen, curWords = 0, []
for w in words:
if curLen + len(w) + len(curWords) <= maxWidth:
curLen += len(w)
curWords.append(w)
else:
ret.append(self.process(curLen, curWords, maxWidth))
curLen, curWords = len(w), [w]
# 单独处理最后一行
if len(curWords) > 0:
cur = ''
for i in range(len(curWords) - 1):
cur = cur + curWords[i] + ' '
cur = cur + curWords[-1]
cur += ' ' * (maxWidth - len(cur))
ret.append(cur)
return ret总结
到这里，我们这道题就算是解决了。看起来非常复杂的问题，解决之后其实也不过只有三十多行而已。不知道有没有比你想的要简单呢？
有没有发现，我们把事情切分之后也非常符合程序设计的惯例？其实代码当中的函数起到的就是一个小模块的作用，而一个复杂的功能也正是这些互相之间彼此独立的小模块组合而成的。从这点上来说，我们做事情化整为零、由繁到简的过程和程序设计过程当中模块设计的道理很多是相通的，所谓大道至简，也许就是这个道理吧。
希望大家喜欢今天的问题，可以的话，请点个关注，给我一点鼓励，也方便获取更多文章。
腾讯云开发者
