java solution based on trie, 71ms. Any suggestions for improvements?


  • 0
    R

    I'm surprised by the those efficient code written in java, can somebody improve my code?

    public class WordDictionary {
        
        class TrieNode {
            TrieNode[] children;
            boolean isWord;
            public TrieNode() {
                children = new TrieNode[26];
                isWord = false;
            }
        }
        
        TrieNode root = new TrieNode();
    
        // Adds a word into the data structure.
        public void addWord(String word) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (node.children[c - 'a'] == null) {
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c - 'a'];
            }
            node.isWord = true;
        }
    
        // Returns if the word is in the data structure. A word could
        // contain the dot character '.' to represent any one letter.
        public boolean search(String word) {
            Queue<TrieNode> queue = new LinkedList<>();
            TrieNode dummy = new TrieNode();
            queue.offer(root);
            queue.offer(dummy);
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (c == '.') {
                    while (!queue.isEmpty()) {
                        TrieNode node = queue.poll();
                        if (node == dummy) break;
                        for (TrieNode n : node.children) {
                            if (n != null) {
                                queue.offer(n);
                            }
                        }
                    }
                } else {
                    while (!queue.isEmpty()) {
                        TrieNode node = queue.poll();
                        if (node == dummy) break;
                        if (node.children[c - 'a'] != null) {
                            queue.offer(node.children[c - 'a']);
                        }
                    }
                }
                queue.offer(dummy);
            }
            while (!queue.isEmpty()) {
                if (queue.poll().isWord) {
                    return true;
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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