Leetcode 664 Solution

This article provides solution to leetcode question 664 (strange-printer)
Categories:
Tags:
Access this page by simply typing in "lcs 664" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/strange-printer

Solution

class Solution:
    def strangePrinter(self, s: str) -> int:
        self.m = {}

        def dfs(s, i, j):
            if i > j:
                return 0

            key = (i, j)
            if key not in self.m:
                ans = dfs(s, i + 1, j) + 1
                for k in range(i + 1, j + 1):
                    if s[i] == s[k]:
                        ans = min(ans, dfs(s, i + 1, k - 1) + dfs(s, k, j))
                self.m[key] = ans
            return self.m[key]

        return dfs(s, 0, len(s) - 1)