0664：奇怪的打印机（★★）

2016-10-25 约 474 字预计阅读 1 分钟次阅读

力扣第 664 题

题目

有台奇怪的打印机有以下两个特殊要求：

打印机每次只能打印由 同一个字符 组成的序列。
每次可以在从起始到结束的任意位置打印新字符，并且会覆盖掉原来已有的字符。

给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

示例 1：

输入：s = "aaabbb"
输出：2
解释：首先打印 "aaa" 然后打印 "bbb"。

示例 2：

输入：s = "aba"
输出：2
解释：首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。

提示：

1 <= s.length <= 100
s 由小写英文字母组成

相似问题：

分析

#1

考虑最后一个字符 s[-1]，只有两种情况
- 单独移除
- 和前面的某个 s[k] 一起移除
  - 必然先移除了 s[k+1:-1] 部分，转为递归子问题
  - 然后移除 s[:k+1]，也转为递归子问题
令 dfs(i,j) 代表 s[i:j] 的最少次数，递归即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def strangePrinter(self, s: str) -> int:
        @cache
        def dfs(i,j):
            if i>j:
                return 0
            res = 1+dfs(i,j-1)
            for k in range(i,j):
                if s[k]==s[j]:
                    res = min(res,dfs(i,k)+dfs(k+1,j-1))
            return res
        return dfs(0,len(s)-1)

337 ms

#2

显然连续相同的字符最后是一起打印的
考虑将连续相同的字符合并得到 A，节省时间。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
    def strangePrinter(self, s: str) -> int:
        @cache
        def dfs(i,j):
            if i>j:
                return 0
            res = 1+dfs(i,j-1)
            for k in range(i,j):
                if A[k]==A[j]:
                    res = min(res,dfs(i,k)+dfs(k+1,j-1))
            return res
        A = [c for c,_ in groupby(s)]
        return dfs(0,len(A)-1)

258 ms

目录

0664：奇怪的打印机（★★）

题目

分析

#1

#2

解答