有一个奇怪的打印机，它有如下两个特别的要求：
1.这个打印机每次只能打印一个由相同字母构成的串。
2. 在每一轮当中，这个打印机可以打印从任意位置开始到任意位置结束的新字母，并且可以覆盖掉原来存在的字母。
给定一个仅包含小写英文字母的字符串，你的任务是计算打印机为了打印出它所需要的最小轮数。
【示例如下】
样例1：
输入: “aaabbb”
输出: 2
解释: 首先打印 “aaa”，然后打印 “bbb”.
样例2：
输入: “aba”
输出: 2
解释: 首先打印 “aaa”，然后从字符串的第二个位置开始打印 “b”，覆盖掉原来存在的字母’a’.
提示：
1 <= s.length <= 100s 由小写英文字母组成题目难度：困难
题目来源： 力扣
def strange_printer(self, s: str) -> int:
"""your code"""
assert strange_printer("aaabbb") == 2
assert strange_printer("aba") == 2
def solution(s:str):
length=len(s)
result = s[0]*length
count = 1
for i in range(1,length):
if result[i]!=s[i]:
last_index =0
for j in range(length-1,0,-1):
if s[j]!=result[j] and s[j]==s[i]:
last_index=j
break
result=result[0:i]+s[i]*(last_index-i+1)+result[last_index+1:]
count+=1
return count
print(solution('aaabbb'))
print(solution('abcbcdcda'))
print(solution('ababcabda'))
class Solution:
def strangePrinter(self,s:str)->int:
if not s:return 0
n = len(s)
dp = [[0]*n for _ in range(n+1)]
for l in range(n):
for i in range(n-l):
j = i+l
dp[i][j] = dp[i+1][j]+1
for k in range(i+1,j+1):
if s[k] == s[i]:
dp[i][j] = min(dp[i][j],dp[i][k-1]+dp[k+1][j])
return dp[0][-1]
assert Solution().strangePrinter("aaabbb") == 2
def strange_printer(s: str) -> int:
"""your code"""
# 打印结果
result = s[0] * len(s)
# 如果打印一次
count = 1
for i in range(1, len(s)):
if result[i] != s[i]:
last_index = 0
for j in range(len(s)-1, 0, -1):
if result[j] != s[j] and s[i] == s[j]:
last_index = j
break
# 重新赋值打印的result,继续循环
result = result[0:i] + s[i] * (last_index - i + 1) + result[last_index + 1:]
count += 1
return count
assert strange_printer("aaabbb") == 2
assert strange_printer("aba") == 2
assert strange_printer("aaaa") == 1
def strange_printer(s: str) -> int:
res_list = ['0' for _ in range(len(s))]
count = 0
l = s + '0'
list1 = [l[i] for i in range(len(l) - 1) if l[i] != l[i + 1]]
dic = {i: i.count(i) for i in list1}
s_list = sorted(dic.items(), key=lambda x: x[1], reverse=True)
for i in range(len(s_list)):
index = s.index(s_list[i][0])
while index < len(s):
if res_list[index] != s_list[i][0]:
if res_list[index] == '0':
res_list[index] = s_list[i][0]
if res_list[index] == s[index]:
s = s[:index] + '0' + s[index + 1:]
index += 1
elif res_list[index] != '0' and s[index] == s_list[i][0]:
res_list[index] = s_list[i][0]
if res_list[index] == s[index]:
s = s[:index] + '0' + s[index + 1:]
index += 1
else:
count += 1
try:
index = s.index(s_list[i][0])
except:
break
else:
index += 1
if index == len(s):
count += 1
return count
assert strange_printer("aaabbb") == 2
assert strange_printer("aba") == 2
assert strange_printer("abab") == 3
assert strange_printer("abababbba") == 4
assert strange_printer("ababaccccccca") == 4