Java Trie


  • 0
    D
    public class Solution {
        private class Trie {
            boolean isWord = false;
            Trie[] next = new Trie[26];
        }
        
        private Trie root;
        
        private void addToTrie(String s) {
            Trie node = root;
            for (char c : s.toCharArray()) {
                if (node.next[c - 'a'] == null) {
                    node.next[c - 'a'] = new Trie();
                }
                node = node.next[c - 'a'];
            }
            node.isWord = true;
        }
        /*
        private boolean searchTrie(String s) {
            Trie node = root;
            for (char c : s.toCharArray()) {
                if (node.next[c - 'a'] == null) return false;
                node = node.next[c - 'a'];
            }
            return node.isWord;
        }
        */
        private boolean searchTrie(char[] ch, int start) {
            Trie node = root;
            for (int i = start; i < ch.length; i++) {
                char c = ch[i];
                if (node.next[c - 'a'] == null) return false;
                node = node.next[c - 'a'];
                if (node.isWord && searchTrie(ch, i + 1)) {
                    return true;
                }
            }
            return start == 0 ? false : node.isWord;
        }
        // Trie: 128ms, 80%
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            // build Trie
            root = new Trie();
            for (String str : words) {
                if (str.equals("")) continue; // use two shorter words
                addToTrie(str);
            }
            // search words
            List<String> list = new ArrayList<>();
            for (String str : words) {
                if (searchTrie(str.toCharArray(), 0)) list.add(str);
            }
            return list;
        }
    }
    

Log in to reply
 

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