Stickers to Spell Word

112.Stickers to Spell Word

Dynamic Programming

String

Problem Statement:

Given an array of strings stickers and a string target, return the minimum number of stickers required to spell out the target string. If it is not possible to form the target, return -1.

Algorithm:

1. Create a frequency map of characters for each sticker to efficiently calculate the characters each sticker can contribute.
2. Use a recursive function with memoization to find the minimum number of stickers required for any substring of the target.
3. In the recursive function:
   • Calculate the character frequency of the current target.
   • For each sticker, reduce the target string by the characters the sticker can contribute.
   • Recurse to find the solution for the reduced target string and update the minimum count.
4. Return the minimum count of stickers required for the full target string, or -1 if not possible.

Complexity:

Time: O(2^m × n), where m is the length of the target and n is the number of stickers | Space: O(2^m).

Java Implementation:

public class Solution {
    public int minStickers(String[] stickers, String target) {
        int m = stickers.length; // Number of stickers
        int[][] mp = new int[m][26]; // Frequency map for stickers
        Map dp = new HashMap<>(); // Memoization map
        
        for (int i = 0; i < m; i++) 
            for (char c : stickers[i].toCharArray()) 
                mp[i][c - 'a']++;
        
        dp.put("", 0); // Base case
        return helper(dp, mp, target);
    }

    private int helper(Map dp, int[][] mp, String target) {
        if (dp.containsKey(target)) return dp.get(target);
        int ans = Integer.MAX_VALUE, n = mp.length;
        int[] tar = new int[26]; // Frequency map for target
        
        for (char c : target.toCharArray()) 
            tar[c - 'a']++;
        
        for (int i = 0; i < n; i++) {
            if (mp[i][target.charAt(0) - 'a'] == 0) continue; // Skip stickers not affecting the target
            
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < 26; j++) {
                if (tar[j] > 0) {
                    for (int k = 0; k < Math.max(0, tar[j] - mp[i][j]); k++) {
                        sb.append((char) ('a' + j));
                    }
                }
            }
            
            int tmp = helper(dp, mp, sb.toString());
            if (tmp != -1) ans = Math.min(ans, 1 + tmp);
        }
        
        dp.put(target, ans == Integer.MAX_VALUE ? -1 : ans);
        return dp.get(target);
    }
}
                

Python Implementation:

def minStickers(stickers, target):
    from collections import Counter
    m = len(stickers)
    mp = [Counter(sticker) for sticker in stickers]
    dp = {"": 0}

    def helper(tar):
        if tar in dp:
            return dp[tar]
        tar_count = Counter(tar)
        ans = float('inf')
        for sticker in mp:
            if sticker[tar[0]] == 0:
                continue
            new_target = ''
            for char, count in tar_count.items():
                if count > sticker[char]:
                    new_target += char * (count - sticker[char])
            tmp = helper(new_target)
            if tmp != -1:
                ans = min(ans, 1 + tmp)
        dp[tar] = -1 if ans == float('inf') else ans
        return dp[tar]

    return helper(target)
                

C++ Implementation:

#include 
#include 
#include 
#include 
using namespace std;

class Solution {
public:
    int minStickers(vector& stickers, string target) {
        int m = stickers.size();
        vector> mp(m, vector(26, 0));
        unordered_map dp;
        
        for (int i = 0; i < m; ++i)
            for (char c : stickers[i])
                mp[i][c - 'a']++;
        
        dp[""] = 0;
        return helper(dp, mp, target);
    }

private:
    int helper(unordered_map& dp, vector>& mp, string target) {
        if (dp.count(target)) return dp[target];
        int ans = INT_MAX;
        vector tar(26, 0);

        for (char c : target) 
            tar[c - 'a']++;
        
        for (auto& sticker : mp) {
            if (sticker[target[0] - 'a'] == 0) continue;

            string s = "";
            for (int i = 0; i < 26; ++i)
                if (tar[i] > sticker[i])
                    s += string(tar[i] - sticker[i], 'a' + i);

            int tmp = helper(dp, mp, s);
            if (tmp != -1) ans = min(ans, 1 + tmp);
        }

        dp[target] = ans == INT_MAX ? -1 : ans;
        return dp[target];
    }
};