Strange Printer

Problem Id: 664 Difficulty: Hard


Intuition

Solution


class Solution:
    def strangePrinter(self, s: str) -> int:
        if not s:
            return 0

        dp = [[None] * len(s) for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = 1
        for l in range(2, len(s) + 1):
            for i in range(len(s) + 1 - l):
                j = i + l - 1
                tmp = dp[i + 1][j] + 1
                for k in range(i + 1, j + 1):
                    if s[i] == s[k]:
                        if k == j:
                            tmp = min(tmp, dp[i][k - 1])
                        else:
                            tmp = min(tmp, dp[i][k - 1] + dp[k + 1][j])
                dp[i][j] = tmp
        return dp[0][len(s) - 1]