Участник:Novitskiy97/Strange Sprinter

Материал из DISCOPAL
Перейти к: навигация, поиск

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

Python 3

class Solution:
    def strangePrinter(self, s: str) -> int:
        if not s: return 0
 
        dd = [[len(s) for i in range(len(s))] for j in range(len(s))]
        dd[0][0] = 1
        for j in range(1, len(s)):
            sj_list = []
            for i in range(j, -1, -1):
                if i == j:
                    dd[i][j] = 1
                    continue
 
                if s[i] == s[j] and (i == 0 or s[i-1] != s[j]):
                    sj_list.append(i)
 
                if s[j] == s[j-1] or s[i] == s[j]:
                    dd[i][j] = dd[i][j-1]
                else:
                    candidates = [dd[x][j] + (dd[i][x-1] if x - 1 >= i else 0) for x in sj_list]
                    candidates.append(dd[i][j-1] + 1)
                    dd[i][j] = min(candidates)
 
        return dd[0][len(s) - 1]