Python DP


  • 0
    class Solution(object):
        def strangePrinter(self, s):
            if not s:
                return 0
            #reduce the input
            fs = s[0]
            for i in range(1, len(s)):
                if s[i] != s[i - 1]:
                    fs += s[i]
            l = len(fs)
            dp = [[0xffffffff for i in range(l)] for j in range(l)]
            for i in range(l):
                dp[i][i] = 1
            for i in range(l):
                for j in range(i - 1, -1, -1):
                    if fs[i] == fs[j]:
                        dp[i][j] = min(dp[i - 1][j + 1] + 1, dp[i - 1][j], dp[i][j + 1])
                    else:
                        for x in range(j + 1, i + 1):
                            dp[i][j] = min(dp[i][x] + dp[x - 1][j], dp[i][j])
            return dp[-1][0]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.