Участник:ArtemTovkes/stickers-to-spell-word

Материал из DISCOPAL
< Участник:ArtemTovkes
Версия от 21:04, 3 декабря 2020; ArtemTovkes (обсуждение | вклад) (Новая страница: «Python3 https://leetcode.com/problems/stickers-to-spell-word/ <code-python> class Solution: def minStickers(self, stickers: List[str], target: str) -> int:…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Python3

https://leetcode.com/problems/stickers-to-spell-word/

class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
 
        t_count = collections.Counter(target)
        A = [collections.Counter(sticker) & t_count for sticker in stickers]
 
        for i in range(len(A)-1, -1, -1):
            if any(A[i] == A[i] & A[j] for j in range(len(A)) if i != j):
                A.pop(i)
 
        stickers = ["".join(s_count.elements()) for s_count in A]
 
        n = len(target)
        N = (1<<n) 
        dp = [math.inf for _ in range(N)]
        dp[0] = 0
 
        for i in range(N):
            if dp[i] == math.inf:
                continue
            for st in stickers:
                j = i
                for ch in st:
                    for k in range(n):
                        if ((j & (1 << k)) == 0) and ch == target[k]:
                            j |= (1 << k)
                            break
                dp[j] = min(dp[j], dp[i] + 1)        
 
        return dp[N-1] if dp[N-1] != math.inf else -1