Java with Trie. Simple and clean


  • 0
    T
    public class WordDictionary {
    
        public class TrieNode {
            TrieNode[] links;
            boolean isEnd;
            final int R = 26;
            TrieNode() {
                links = new TrieNode[R];
            }
        }
        
        private TrieNode root;
        
        /** Initialize your data structure here. */
        public WordDictionary() {
            root = new TrieNode();
        }
        
        /** Adds a word into the data structure. */
        public void addWord(String word) {
            TrieNode node = root;
            int len = word.length();
            for (int i = 0 ; i < len ; i++) {
                char ch = word.charAt(i);
                if (node.links[ch - 'a'] == null) node.links[ch - 'a'] = new TrieNode();
                node = node.links[ch - 'a'];
            }
            node.isEnd = 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) {
            return search(word.toCharArray(), 0, root);
        }
        
        private boolean search(char[] word, int index, TrieNode node) {
            if (word.length == index) return node.isEnd;
            
            if (word[index] != '.') 
                return node.links[word[index] - 'a'] != null && search(word, index + 1, node.links[word[index] - 'a']);
            else {
                int len = node.links.length;
                for (int i = 0; i < len ; i++) {
                    if (node.links[i] != null && search(word, index + 1, node.links[i])) return true;
                }
                return false;
            }
        }
    }
    

Log in to reply
 

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