DP solution accelerated with Trie pre-processing


  • 0

    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];
        	}
        }
    

Log in to reply
 

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