691.md

691 Stickers to Spell Word

Description

link

---

Solution : MEMO + DFS

DP[s] = min(1 + DP[reduced_s]) for all stickers

here reduced_s is a new string after certain sticker applied

Optimization: If the target can be spelled out by a group of stickers, at least one of them has to contain character target[0]. So I explicitly require next sticker containing target[0], which significantly reduced the search space.

---

Code

Complexity T : O(N^2) M : O(N^2)

class Solution:
    def minStickers(self, stickers, target):
        """
        :type stickers: List[str]
        :type target: str
        :rtype: int
        """
        lens = len(stickers)
        char_count = [[0] * 26 for i in range(lens)]
        for i in range(lens):
            for c in stickers[i]:
                char_count[i][ord(c)-ord('a')] += 1  # count every single characters for each stickers
        
        memo = {}
        memo[""] = 0
        
        def dfs(memo, char_count, target):
            if target in memo:
                return memo[target]

            n = len(char_count)
            tar = [0] * 26

            for c in target:
                tar[ord(c) - ord('a')] += 1  # count every single characters for target
 
            ans = float("inf")  # temp ans

            for i in range(n):
                if char_count[i][ord(target[0]) - ord('a')] == 0:  # if there is no such character(target[0]) in stickers[i]
                    continue

                s = ''
                for j in range(26):
                    if tar[j] > char_count[i][j]:  # if times of c in target > times in stickers[i]
                        s += chr(ord('a') + j) * (tar[j] - char_count[i][j])  # put less c into temp target(s)

                tmp = dfs(memo, char_count, s)
                if (tmp != -1):
                    ans = min(ans, 1 + tmp)
            memo[target] = -1 if ans == float("inf") else ans
            return memo[target]
                
        return dfs(memo, char_count, target)