# DP solution accelerated with Trie pre-processing

• The idea is simple as based on the winner's dp solution. (The DP solution itself took me a while to understand)
I just implement a Trie structure to pre-process the stickers and generate a set containing `only relevant characters` and `no words overlap`. The simulation time is `182 ms` based on the current 100 test cases.

``````    public int minStickers(String[] stickers, String target) {
if (target == null || stickers == null) {
return -1;
}
if (target.length() == 0) {
return 0;
}
Trie trie = new Trie();
trie.setTarget(target);
for (String sticker : stickers) trie.insert(sticker);
int res = helper(trie.set, target);
return res;
}

private int helper(Set<String> stickers, String target) {
int n = target.length();
int[] dp = new int[1 << n];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int state = 0; state < (1 << n); state++) {
if (dp[state] == -1) continue;
for (String sticker : stickers) {
int now = state;
for (char c : sticker.toCharArray()) {
for (int i = 0; i < n; i++) {
if (((now >> i) & 1) == 0 && c == target.charAt(i)) {
now = now | (1 << i);
// Use c for this digit
break;
}
}
if (dp[now] == -1 || dp[now] > (1 + dp[state])) {
dp[now] = 1 + dp[state];
}
}
}
}
return dp[(1 << n) - 1];
}

public static class Trie {
TrieNode root = new TrieNode();
Set<String> set = new HashSet<>();
int[] dict = new int[26];

public void setTarget(String target) {
for (char c : target.toCharArray()) {
dict[c - 'a']++;
}
}

public void insert(String s) {
if (s == null || s.length() == 0) return;
char[] chs = s.toCharArray();
Arrays.sort(chs);
TrieNode node = root;
StringBuilder sb = new StringBuilder();
for (char c : chs) {
if (dict[c - 'a'] == 0) continue;
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
sb.append(c);
node = node.children[c - 'a'];
if (node.end) {
set.remove(sb.toString());
node.end = false;
}
}
for (TrieNode next : node.children) {
if (next != null) return;
}
node.end = true;
set.add(sb.toString());
}
}

private static class TrieNode {
TrieNode[] children;
boolean end;
public TrieNode() {
children = new TrieNode[26];
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.