Java Trie + memorized dfs, 112ms


  • 0
    H

    eg: ["cat", "dog", "catdog"]
    search for cat:
    dfs(cat, root, level-0) --> dfs("", root, level-1) --> return false;

    search for dog:
    dfs(dog, root, level-0) --> dfs("", root, level-1) --> return false;

    search for catdog:
    dfs(catdog, root, level-0) --> dfs(dog, root, level-1) --> dfs("", root, level-2) return true;

    Note:
    // don't store level-0 because it will mess up with level-1 and above
    // dfs(dog, level-0) will return false, but dfs(catdog, level-0)-->dfs(dog, level-1) will return true

        // Trie: 224ms, 59%
        // Trie + hashMap: 112ms, 92%
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            Trie root = new Trie();
            for (String s : words) {
                addToTrie(root, s);
            }
            List<String> result = new ArrayList();
            for (String s : words) {
                if (dfs(s, root, 0)) {
                    result.add(s);
                }
            }
            return result;
        }
        Map<String, Boolean> map = new HashMap(); 
        
        private boolean dfs(String s, Trie root, int level) {
            if (s.length() == 0 && level > 1) {
                return true;
            }
            if (level > 0 && map.containsKey(s)) {
                return map.get(s);
            }
            Trie node = root;
            for (int i = 0; i < s.length(); i++) {
                node = node.nodes[s.charAt(i) - 'a'];
                if (node == null) break;
                if (node.str != null) {
                    if (dfs(s.substring(i + 1), root, level + 1)) {
                        map.put(s, true);
                        return true;
                    }
                }
            }
            if (level > 0) {
                // don't store level-0 because it will mess up with level-1 and above
                // dfs(dog, level-0) will return false, but dfs(catdog, level-0)-->dfs(dog, level-1) will return true
                  map.put(s, false);
             }
            return false;
        }
        
        private void addToTrie(Trie root, String s) {
            Trie node = root;
            for (char c : s.toCharArray()) {
                if (node.nodes[c- 'a'] == null) {
                    node.nodes[c - 'a'] = new Trie();
                }
                node = node.nodes[c- 'a'];
            }
            node.str = s;
        }
        
        class Trie {
            String str;
            Trie[] nodes = new Trie[26];
            public Trie() { }
        }
    }
    
    

Log in to reply
 

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