aboutsummaryrefslogtreecommitdiff
path: root/strange_printer.py
diff options
context:
space:
mode:
Diffstat (limited to 'strange_printer.py')
-rw-r--r--strange_printer.py35
1 files changed, 35 insertions, 0 deletions
diff --git a/strange_printer.py b/strange_printer.py
new file mode 100644
index 0000000..abc8899
--- /dev/null
+++ b/strange_printer.py
@@ -0,0 +1,35 @@
+# 664. Strange Printer
+
+"""
+there is a strange printer with the following two special properties:
+- 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 eding
+at any place and will cover the origin existing characters given a string
+'s', return the minimum number of turns the printer needed to print it.
+"""
+
+
+class Solution(object):
+ def strangePrinter(self, s):
+ """
+ :type s: str
+ :rtype: int
+ """
+ n = len(s)
+ dp = [[0] * n for _ in range(n)]
+ for i in range(n - 1, -1, -1):
+ dp[i][i] = 1
+ for j in range(i + 1, n):
+ if s[i] == s[j]:
+ dp[i][j] = dp[i][j - 1]
+ else:
+ dp[i][j] = dp[i][j - 1] + 1
+ for k in range(i, j):
+ dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])
+ return dp[0][n - 1]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.strangePrinter("aaabbb"))
+ print(obj.strangePrinter("aba"))