Java Two solutions: Trie and Non-Trie, both ~150ms DFS + HashMap Memorization with detail explanation


  • 0

    For a certain string s we do a DFS to try to decompose it into multiple shorter words. At each DFS step we basically try to find the matched prefix with ascending length that way we can guarantee that we found a way to decompose before we encounter s itself since it's the last one in the for loop. The value returned by DFS is 0 - if s is neither in the array nor can be decomposed; 1 - s cannot be decomposed but is in the array; > 1 s can be decomposed. We use HashMap to memorize the result to expedite future DFS on the same string s. The two solution differs in how to find matched prefix - using HashSet or Trie.
    The first use HashSet to find matched prefix:

        private HashMap<String, Integer> map;
        private HashSet<String> set;
    
        private int dfs(String s) {
            if (map.containsKey(s)) return map.get(s);
            for (int i = 0; i < s.length(); i++) {
                if (set.contains(s.substring(0, i+1))) {
                    int k = dfs(s.substring(i+1));
                    if (k != 0) {
                        map.put(s, 1 + k);
                        return 1 + k;
                    }
                }
            }
            if (set.contains(s)) {
                map.put(s, 1);
                return 1;
            } else {
                map.put(s, 0);
                return 0;
            }
        }
    
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            List<String> result = new LinkedList<>();
            if (words.length < 2) return result;
            map = new HashMap<>();
            for (String s :  words) set.add(s);
            for (String s : words) {
                if (dfs(s) > 1) result.add(s);
            }
            return result;
        }
    

    The second use Trie to find matched Prefix:

    private Trie root;
        private HashMap<String, Integer> map;
        private class Trie {
            private Trie[] children = new Trie[26];
            private boolean isWord = false;
        }
        private void addWord(Trie root, String word) {
            Trie curr = root;
            for (int i = 0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';
                if (curr.children[index] == null) curr.children[index] = new Trie();
                curr = curr.children[index];
            }
            curr.isWord = true;
        }
        private int dfs(String s) {
            if (map.containsKey(s)) return map.get(s);
            if (s.length() == 0) return 0;
            Trie curr = root;
            for (int i = 0; i < s.length(); i++) {
                int index = s.charAt(i) - 'a';
                if (curr.children[index] == null) break;
                curr = curr.children[index];
                if (curr.isWord) {
                    if (i == s.length() - 1) {
                        map.put(s, 1);
                        return 1;
                    } else {
                        int k = dfs(s.substring(i+1));
                        if (k != 0) {
                            map.put(s, 1+k);
                            return 1+k;
                        }
                    }
                }
            }
            map.put(s, 0);
            return 0;
        }
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            List<String> result = new LinkedList<>();
            if (words.length < 2) return result;
            root = new Trie();
            map = new HashMap<>();
            for (String s : words) addWord(root, s);
            for (String s: words)
                if (dfs(s) > 1) result.add(s);
            return result;
        }
    

Log in to reply
 

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