Google 面试题：奇怪的打印机

转载时间：2022.04.02（原文发布时间：2017.10.18）

转载作者：36氪企服点评小编

阅读次数：2次

作者｜陈近南

编辑｜Winnie li

专栏｜九章算法，高阶IT求职教育平台，官网www.jiuzhang.com

题目描述：

一个奇怪的打印机打印时遵守以下两个特殊的条件：

每次只能打印同一个字符组成的连续序列。
每次打印可以在任何位置开始，在任何位置结束，打印的字符会将原来已有的字符覆盖。

给定一个只包含小写字母的字符串，你的任务是计算用该打印机打印出这个字符串所需的最少打印次数。字符串长度不超过100。

样例

Example 1:

输入: "aaabbb"

输出: 2

说明: 先打印"aaa"，再打印"bbb"。

Example 2:

输入: "aba"

输出: 2

说明: 先打印"aaa"，再在中间的位置打印"b"覆盖之前的”a”。

解题思路

1、一个简单的想法是，给出的字符串有几段不同的字符，就打印几次，不考虑打印覆盖的情况。比如aabbc，那就打印三次。这是一种贪心策略，但是在某些情况下不能取得最优解，比如aabba，我们先打印aaaaa，然后打印bb，只需要两次。

2、那么搜索可行吗？我们每次搜索起点在最左边的打印区间（需要搜索终点），我们发现通过记录目前正确打印到了哪个位置，我们可以直接求的下一次打印的起点。因为我们总需要从第一个出错的位置开始打印。这样做是可行的，但是复杂度是指数级别，仍有优化的可能性。

3、结合之前两种思路，我们来观察总结一下，打印出来的字符串的特点：

假设某一次打印机打印了若干个'a'，像这样：”aaaaaa”，在这之后打印的字符，无非是三种情况：

● 在这段字符串的内部打印，但是不覆盖这段字符串的一端，例如”abbbaa”、”abbada”。

● 在这段字符串的外部打印，完全不覆盖这段字符串，例如”bbaaaaaa”、”bbaaaaaaccc”。

● 覆盖这段字符串的一端，例如”baaaaa”、”baaacccccc”。

上面所说的第三种情况，看起来就像后来的字符都打印在”a”组成的字符串的外部。事实上，如果打印了一串字符串后，再打印一些字符覆盖这段字符串的端点会造成浪费，也就是说被覆盖的这字符串的部分一开始完全没有必要打印，也不会对最终打印次数造成影响。所以，我们可以假定，打印时不存在浪费，也就是说某次打印可以覆盖前面某一次打印的（不包含端点的）内部，也可以不覆盖，但是不能覆盖前面某一次打印的端点。

4、对于一个已知的目标字符串s，我们考虑打印出这个字符串最左边的字符s[0]的那次打印，我们总可以在打印方案中，把该次打印放到第一次打印。可以这样做的理由是，由于c中的假定，其它的打印要么在这次打印的内部（不包含端点），要么在这次打印的外部，并且由于包含目标字符串的最左端点，所以这次打印也不可能在别的打印的内部。这样一来我们就可以枚举包含s[0]的那次打印的长度L，然后把原目标字符串分为s[0 ~ L-1]和s[L ~ N-1]（设原字符串长度为N），其中，由a中的假定可知s[0]==s[L-1]必须成立（因为端点不被覆盖）。s[0 ~ L-1]的最少打印次数实际等于 s[1 ~ L-1]的最少打印次数（也等于s[0 ~ L-2]的最少打印次数），这是因为打印出其中一个字符串的打印方案可以稍加变动变成另一个的打印方案而不改变打印次数（读者可以想一想是如何变动的）。s[L ~ N-1]的打印与前面字符的打印没有关系，可以看成一个新的目标字符串，用同样的方法分析计算。有两个特殊情况：L=1时，s[0]==s[L-1]必然成立，这时的答案为1 + s[1 ~ N-1]的最小打印次数；L=N时，应满足s[0]==s[L-1]==s[N-1]，即左右两端点相等，答案为s[1 ~ N-1]的最小打印次数。

5、分别计算出s[1 ~ L-1]、s[L ~ N-1]的最小打印次数并相加得到特定L下的打印次数，枚举所有L，对得到的答案取最小值即可得到最终答案。这样把一个区间分成两个小的连续区间求解的方法属于区间型动态规划，状态表示为f[i][j]表示从i到j这段子串最少打印次数。具体可以采用递推的方式（应先从小到大枚举区间的长度，因为长区间的答案是由短区间的答案确定的）把所有可能的区间的答案都算出来，也可采用记忆化搜索的递归形式实现，边界条件为：长度为1的区间的字符串最少打印次数为1。枚举所有区间的时间复杂度为O(n^2)，枚举分段点的时间复杂度为O(n)，故总的时间复杂度为O(n^3)，额外空间复杂度为O(n^2)。