There is a strange printer with the following two special requirements:
- The printer can only print a sequence of the same character each time.
- At each turn, the printer can print new characters starting from and ending at any places, and will cover the original existing characters.
Given a string consists of lower English letters only, your job is to count the minimum number of turns the printer needed in order to print it.
Example 1:
Input: "aaabbb" Output: 2 Explanation: Print "aaa" first and then print "bbb".
Example 2:
Input: "aba" Output: 2 Explanation: Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.
Hint: Length of the given string will not exceed 100.
有台奇怪的打印机有以下两个特殊要求:
- 打印机每次只能打印同一个字符序列。
- 每次可以在任意起始和结束位置打印新字符,并且会覆盖掉原来已有的字符。
给定一个只包含小写英文字母的字符串,你的任务是计算这个打印机打印它需要的最少次数。
示例 1:
输入: "aaabbb" 输出: 2 解释: 首先打印 "aaa" 然后打印 "bbb"。
示例 2:
输入: "aba" 输出: 2 解释: 首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。
提示: 输入字符串的长度不会超过 100。
116ms
1 class Solution { 2 func strangePrinter(_ s: String) -> Int { 3 var c = [Character]() 4 var pre : Character = " " 5 for (_, char) in s.enumerated() { 6 if char != pre { 7 c.append(char) 8 pre = char 9 } 10 } 11 var l = [[Int]](repeating:[Int](repeating: 0, count:c.count) , count:c.count) 12 return turn(c, 0, c.count - 1, &l) 13 } 14 15 func turn(_ c: [Character], _ i: Int, _ j: Int, _ l: inout [[Int]]) -> Int { 16 if i > j { 17 return 0 18 } 19 if l[i][j] > 0 { 20 return l[i][j] 21 } 22 var ans = turn(c, i, j-1, &l) + 1 23 for k in i ..< j { 24 if c[k] == c[j] { 25 ans = min(ans, turn(c, i, k, &l) + turn(c, k+1, j-1, &l)) 26 } 27 } 28 l[i][j] = ans 29 return ans 30 } 31 }
Runtime: 196 ms Memory Usage: 19.9 MB
1 class Solution { 2 func strangePrinter(_ s: String) -> Int { 3 if s.isEmpty {return 0} 4 var arr:[Character] = Array(s) 5 var n:Int = s.count 6 var dp:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:n),count:n) 7 for i in (0...(n - 1)).reversed() 8 { 9 if(n < i) {continue} 10 for j in i..<n 11 { 12 dp[i][j] = (i == j) ? 1 : (1 + dp[i + 1][j]) 13 if(j < i + 1) {continue} 14 for k in (i + 1)...j 15 { 16 if arr[k] == arr[i] 17 { 18 dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k][j]) 19 } 20 } 21 } 22 } 23 return (n == 0) ? 0 : dp[0][n - 1] 24 } 25 }