We are given n different types of stickers. Each sticker has a lowercase English word on it.

You would like to spell out the given string target by cutting individual letters from your collection of stickers and rearranging them. You can use each sticker more than once if you want, and you have infinite quantities of each sticker.

Return the minimum number of stickers that you need to spell out target. If the task is impossible, return -1.

Note: In all test cases, all words were chosen randomly from the 1000 most common US English words, and target was chosen as a concatenation of two random words.

&nbsp;
Example 1:

Input: stickers = ["with","example","science"], target = "thehat"
Output: 3
Explanation:
We can use 2 "with" stickers, and 1 "example" sticker.
After cutting and rearrange the letters of those stickers, we can form the target "thehat".
Also, this is the minimum number of stickers necessary to form the target string.


Example 2:

Input: stickers = ["notice","possible"], target = "basicbasic"
Output: -1
Explanation:
We cannot form the target "basicbasic" from cutting letters from the given stickers.


&nbsp;
Constraints:


	n == stickers.length
	1 &lt;= n &lt;= 50
	1 &lt;= stickers[i].length &lt;= 10
	1 &lt;= target.length &lt;= 15
	stickers[i] and target consist of lowercase English letters.


from functools import lru_cache
from collections import Counter
class Solution(object):
    def minStickers(self, stickers, target):
        counter = [Counter(sticker) for sticker in stickers] 
        n = len(counter)
        @lru_cache(None)
        def dfs(target):
            if not target: return 0
            targ_counter = Counter(target)
            res = float('inf')
            #using sticker[i] if it contains the first letter of target
            for i in range(n):
                if counter[i][target[0]] == 0:
                    continue
                s = ''
                for j in 'abcdefghijklmnopqrstuvwxyz':
                    s += j*max(targ_counter[j] - counter[i][j], 0) 
                res = min(res, 1 + dfs(s)) if dfs(s) != -1 else res
            return -1 if res == float('inf') else res
        return dfs(target)
class Solution {
    HashMap<String,HashMap<Character,Integer>>map;
    public int minStickers(String[] stickers, String target) {
        map = new HashMap<>();
        for(String sticker:stickers){
            HashMap<Character,Integer> temp = new HashMap<>();
            for(char ch:sticker.toCharArray())
                temp.put(ch,temp.getOrDefault(ch,0)+1);
            map.put(sticker,temp);
        }
        int count = memoization(target,new HashMap<>());
        return count<1||count>=Integer.MAX_VALUE?-1:count;
    }
    public int memoization(String target, HashMap<String, Integer>dpmap){
        if(target.length()==0)return 0;
        if(dpmap.containsKey(target)) return dpmap.get(target);
        int count = Integer.MAX_VALUE;
        for(String str: map.keySet()){
              HashMap<Character,Integer> xd = new HashMap(map.get(str));
              String temp = target;
              char ch = temp.charAt(0);
              if(xd.containsKey(ch)){
                 for(int i =0;i<temp.length();i++){
                     ch = temp.charAt(i);
                     if(xd.containsKey(ch) && xd.get(ch)>0){
                         xd.put(ch,xd.get(ch)-1);
                         temp = temp.substring(0,i)+temp.substring(i+1);
                         i--;
                     }
                 }
                  if(temp.length()!=target.length()){
                      count  = Math.min(count,1+memoization(temp,dpmap));
                      dpmap.put(target,count);    
                  }
              }
        }
        return count;
    }
}
class Solution {
public:
    int dp[50][1<<15] ;
    int solve(int ind, int mask, vector<string>& stickers, string& target)
    {
        if (mask == 0)
            return 0 ;
        if (ind == stickers.size())
            return 1e8 ;
        if (dp[ind][mask] != -1)
            return dp[ind][mask] ;
        vector<int> mp(26, 0);
        bool flag = false ;
        int ans = 1e8 ;
        for(int i = 0; i < stickers[ind].size(); i++)
            mp[stickers[ind][i]-'a'] ++ ;
        for(int i= 0; i < target.size(); i++)
        {
            if (mp[target[i]-'a'] > 0 && (mask & (1<<i)))
            {
                flag = true ;
                break ;
            }
        }
        if (flag) // Check if we can use any of the characters in sticker[ind]
        {
            int tempMask = mask ;
            for(int i = 0; i < target.size(); i++)
            {
                if (mp[target[i]-'a'] > 0 && (tempMask & (1<<i)))
                {
                    tempMask = tempMask ^ (1<<i) ;
                    mp[target[i]-'a'] -- ;
                }
            }
            ans = min(ans, 1+solve(ind, tempMask, stickers, target)) ; // Take those characters, and make call on same index
        }
        ans = min(ans, solve(ind+1, mask, stickers, target)) ; // Skip sticker[ind] and proceed
        return dp[ind][mask] = ans;
    }

    int minStickers(vector<string>& stickers, string target) {
        int n = target.size();
        memset(dp, -1, sizeof(dp)) ;
        int ans = solve(0, (1<<n)-1, stickers, target) ;
        if (ans == 1e8)
            return -1 ;
        return ans ;
    }
};
/**
 * @param {string[]} stickers
 * @param {string} target
 * @return {number}
 */

// Backtracking
var minStickers = function(stickers, target) {
    //* Inits *//
    let dp = new Map();

    //* Helpers *//
    const getStringDiff = (str1, str2) => {
        for(let c of str2) {
            if(str1.includes(c)) str1 = str1.replace(c, '');
        }
        return str1;
    }
    dp.set('', 0);

    //* Main *//
    function calcStickers(restStr) {
        // if(restStr === "") return 0; <-- without memoization
        if (dp.has(restStr)) return dp.get(restStr);
        let res = Infinity;

        for (let s of stickers.filter(s => s.includes(restStr[0]))) { // if current sticker does not contain the FIRST char, continue
            let str = getStringDiff(restStr, s); //aabbc - bc = aab
            res = Math.min(res, 1 + calcStickers(str)); // RECURSE.... calculate min stickers for the remaining letters.. try combination for all strings and get min
        }

        dp.set(restStr, res === Infinity || res === 0 ? -1 : res); //Memoize the result in dp;
        return dp.get(restStr);
        // return res; <-- without memoization
    }
    return calcStickers(target)
}
Stickers to Spell Word