691. Stickers to Spell Word - Explanation

1. Dynamic Programming (Top-Down) - I

class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        stickCount = []
        for s in stickers:
            stickCount.append({})
            for c in s:
                stickCount[-1][c] = 1 + stickCount[-1].get(c, 0)

        dp = {}

        def dfs(t, stick):
            if t in dp:
                return dp[t]
            res = 1 if stick else 0
            remainT = ""
            for c in t:
                if c in stick and stick[c] > 0:
                    stick[c] -= 1
                else:
                    remainT += c
            if remainT:
                used = float("inf")
                for s in stickCount:
                    if remainT[0] not in s:
                        continue
                    used = min(used, dfs(remainT, s.copy()))
                dp[remainT] = used
                res += used
            return res

        res = dfs(target, {})
        return res if res != float("inf") else -1

Time & Space Complexity

Time complexity: $O(m * k *2 ^ n)$
Space complexity: $O(m * k + 2 ^ n)$

Where $n$ is the length of the target string, $m$ is the number of stickers and $k$ is the average length of each sticker.

2. Dynamic Programming (Top-Down) - II

class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        tmp = [c for c in target]
        target = ''.join(sorted(tmp))
        stickCount = []
        for s in stickers:
            stickCount.append(Counter(s))

        dp = {}
        dp[""] = 0

        def dfs(t):
            if t in dp:
                return dp[t]

            tarMp = Counter(t)
            res = float("inf")
            for s in stickCount:
                if t[0] not in s:
                    continue
                remainT = []
                for c in tarMp:
                    if tarMp[c] > s[c]:
                        remainT.extend([c] * (tarMp[c] - s[c]))

                remainT = ''.join(sorted(remainT))
                res = min(res, 1 + dfs(remainT))

            dp[t] = res
            return res

        ans = dfs(target)
        return -1 if ans == float("inf") else ans

Time & Space Complexity

Time complexity: $O(m * k *2 ^ n)$
Space complexity: $O(m * k + 2 ^ n)$

Where $n$ is the length of the target string, $m$ is the number of stickers and $k$ is the average length of each sticker.

3. Dynamic Programming (Bottom-Up)

class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        n = len(target)
        N = 1 << n
        dp = [-1] * N
        dp[0] = 0

        for t in range(N):
            if dp[t] == -1:
                continue
            for s in stickers:
                nextT = t
                for c in s:
                    for i in range(n):
                        if target[i] == c and not ((nextT >> i) & 1):
                            nextT |= 1 << i
                            break
                if dp[nextT] == -1 or dp[nextT] > dp[t] + 1:
                    dp[nextT] = dp[t] + 1
        return dp[N - 1]

Time & Space Complexity

Time complexity: $O(n * m * k *2 ^ n)$
Space complexity: $O(2 ^ n)$

Where $n$ is the length of the target string, $m$ is the number of stickers and $k$ is the average length of each sticker.