1
class Solution {
2
  HashMap<String, HashMap<Character, Integer>> map;
3

4
  public int minStickers(String[] stickers, String target) {
5
    map = new HashMap<>();
6
    for (String sticker : stickers) {
7
      HashMap<Character, Integer> temp = new HashMap<>();
8
      for (char ch : sticker.toCharArray()) temp.put(ch, temp.getOrDefault(ch, 0) + 1);
9
      map.put(sticker, temp);
10
    }
11
    int count = memoization(target, new HashMap<>());
12
    return count < 1 || count >= Integer.MAX_VALUE ? -1 : count;
13
  }
14

15
  public int memoization(String target, HashMap<String, Integer> dpmap) {
16
    if (target.length() == 0) return 0;
17
    if (dpmap.containsKey(target)) return dpmap.get(target);
18
    int count = Integer.MAX_VALUE;
19
    for (String str : map.keySet()) {
20
      HashMap<Character, Integer> xd = new HashMap(map.get(str));
21
      String temp = target;
22
      char ch = temp.charAt(0);
23
      if (xd.containsKey(ch)) {
24
        for (int i = 0; i < temp.length(); i++) {
25
          ch = temp.charAt(i);
26
          if (xd.containsKey(ch) && xd.get(ch) > 0) {
27
            xd.put(ch, xd.get(ch) - 1);
28
            temp = temp.substring(0, i) + temp.substring(i + 1);
29
            i--;
30
          }
31
        }
32
        if (temp.length() != target.length()) {
33
          count = Math.min(count, 1 + memoization(temp, dpmap));
34
          dpmap.put(target, count);
35
        }
36
      }
37
    }
38
    return count;
39
  }
40
}