1
/**
2
 * @param {string[]} stickers
3
 * @param {string} target
4
 * @return {number}
5
 */
6

7
// Backtracking
8
var minStickers = function (stickers, target) {
9
  //* Inits *//
10
  let dp = new Map();
11

12
  //* Helpers *//
13
  const getStringDiff = (str1, str2) => {
14
    for (let c of str2) {
15
      if (str1.includes(c)) str1 = str1.replace(c, "");
16
    }
17
    return str1;
18
  };
19
  dp.set("", 0);
20

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

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

33
    dp.set(restStr, res === Infinity || res === 0 ? -1 : res); //Memoize the result in dp;
34
    return dp.get(restStr);
35
    // return res; <-- without memoization
36
  }
37
  return calcStickers(target);
38
};