691. Stickers to Spell Word

Hard

Description

給定 n 種貼紙（每種無限供應），每張貼紙上有若干小寫字母。要拼出目標字串 target，最少需要幾張貼紙？如果無法拼出，回傳 -1。

Example:

Input: stickers = [“with”,“example”,“science”], target = “thehat” Output: 3

Intuition#

用 bitmask 表示 target 中哪些字元已被覆蓋，BFS/DP 找最少貼紙數。

target 最長 15 個字元，可以用 bitmask 表示收集狀態
dp[mask] = 覆蓋 mask 所代表的字元所需的最少貼紙數
對每個狀態嘗試每張貼紙，看能覆蓋哪些尚未收集的字元
優化：每次只需嘗試能覆蓋當前 mask 中第一個未收集字元的貼紙

Approaches#

1: Bitmask DP (Top-Down)#

概念: 記憶化搜尋，每個 mask 狀態嘗試每張貼紙
時間複雜度: O(2^n * m * n) 其中 n = target 長度, m = 貼紙數
空間複雜度: O(2^n)

class Solution {
    fun minStickers(stickers: Array<String>, target: String): Int {
        val n = target.length
        val full = (1 shl n) - 1
        val memo = IntArray(1 shl n) { -2 }
        memo[0] = 0

        // 預處理每張貼紙的字元頻率
        val stickerCounts = stickers.map { s ->
            IntArray(26).also { cnt -> s.forEach { cnt[it - 'a']++ } }
        }

        fun dp(mask: Int): Int {
            if (mask == full) return 0
            if (memo[mask] != -2) return memo[mask]

            // 找第一個未覆蓋的字元
            var first = -1
            for (i in 0 until n) {
                if (mask and (1 shl i) == 0) { first = i; break }
            }

            var best = Int.MAX_VALUE
            for (cnt in stickerCounts) {
                // 只嘗試包含第一個未覆蓋字元的貼紙
                if (cnt[target[first] - 'a'] == 0) continue
                val avail = cnt.copyOf()
                var newMask = mask
                for (i in 0 until n) {
                    if (newMask and (1 shl i) == 0 && avail[target[i] - 'a'] > 0) {
                        newMask = newMask or (1 shl i)
                        avail[target[i] - 'a']--
                    }
                }
                val sub = dp(newMask)
                if (sub != -1) best = minOf(best, sub + 1)
            }
            memo[mask] = if (best == Int.MAX_VALUE) -1 else best
            return memo[mask]
        }
        return dp(0)
    }
}

⭐2: Bitmask DP (Bottom-Up BFS-style)#

概念: 從空集合出發，逐步嘗試加貼紙擴展狀態
時間複雜度: O(2^n * m * n)
空間複雜度: O(2^n)

class Solution {
    fun minStickers(stickers: Array<String>, target: String): Int {
        val n = target.length
        val full = (1 shl n) - 1
        val dp = IntArray(1 shl n) { Int.MAX_VALUE }
        dp[0] = 0

        val stickerCounts = stickers.map { s ->
            IntArray(26).also { cnt -> s.forEach { cnt[it - 'a']++ } }
        }

        for (mask in 0 until (1 shl n)) {
            if (dp[mask] == Int.MAX_VALUE) continue
            for (cnt in stickerCounts) {
                val avail = cnt.copyOf()
                var newMask = mask
                for (i in 0 until n) {
                    if (newMask and (1 shl i) == 0 && avail[target[i] - 'a'] > 0) {
                        newMask = newMask or (1 shl i)
                        avail[target[i] - 'a']--
                    }
                }
                dp[newMask] = minOf(dp[newMask], dp[mask] + 1)
            }
        }
        return if (dp[full] == Int.MAX_VALUE) -1 else dp[full]
    }
}

🔑 Takeaways#

Pattern: Bitmask DP — 用位元遮罩表示子集的收集狀態
關鍵技巧: 剪枝策略 — 只嘗試能覆蓋「第一個未收集字元」的貼紙，大幅減少搜索空間