Yet another Java Trie Solution (113 ms)


  • 0
    J

    I sort the input array by its length first, and in the iteration, first check if it is valid in current Trie tree, and then insert its value into the tree. It is kind of trade off since the search space is probably reduced, but there is an overhead of sorting.

    public class Solution {
        class TrieNode {
            TrieNode[] children;
            boolean isWord;
            TrieNode() {
                children = new TrieNode[26];
                isWord = false;
            }
    
            private void insert(char[] chars, int index, TrieNode parent) {
                char c = chars[index];
                TrieNode node = parent.children[c - 'a'];
                if (node == null) {
                    node = new TrieNode();
                    parent.children[c - 'a'] = node;
                }
                if (index == chars.length - 1) {
                    node.isWord = true;
                    return;
                }
                insert(chars, index + 1, node);
            }
    
            public void insert(String word) {
                if (word.isEmpty()) return;
                char[] chars = word.toCharArray();
                insert(chars, 0, this);
            }
    
            private boolean buildable(char[] chars, int ind, TrieNode parent, TrieNode root) {
                char c = chars[ind];
                TrieNode next = parent.children[c - 'a'];
                if (next == null) {
                    return false;
                }
                if (ind == chars.length - 1) {
                    return next.isWord;
                }
                if (next.isWord) {
                    return buildable(chars, ind + 1, root, root) || buildable(chars, ind + 1, next, root);
                }
                return buildable(chars, ind + 1, next, root);
            }
    
            public boolean buildable(String word) {
                if (word.isEmpty()) return false;
                char[] chars = word.toCharArray();
                return buildable(chars, 0, this, this);
            }
        }
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            List<String> res = new ArrayList<>();
            if (words == null || words.length < 2) return res;
            Arrays.sort(words, new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return o1.length() - o2.length();
                }
            });
            TrieNode root = new TrieNode();
            for (int i = 0; i < words.length; i++) {
                if (root.buildable(words[i])) res.add(words[i]);
                root.insert(words[i]);
            }
            return res;
        }
    }
    

Log in to reply
 

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