diff options
Diffstat (limited to 'strange_printer.py')
-rw-r--r-- | strange_printer.py | 35 |
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")) |