Simple Trie in Java


  • 0
    L

    A few things about Trie may help to understand it better:

    1. A trie node maintains a map of character and another TrieNode.
    2. It will be easier to keep a root node and do everything relative to it.
    3. A trie node represents all mappings to a single character without adding that character explicitly. We also use an empty trie node with isend=true to mark the end of the word. For example, to add the word "bad", here is what happens:

    root "b"-> TrieNode of "a"
    "a" --> TrieNode of "d"
    "d" -> TrieNode of isEnd=true.

    public class WordDictionary {
    
        private final TrieNode root = new TrieNode();
        /** Adds a word into the data structure. */
        public void addWord(String word) {
            root.add(word,0);
        }
        
        /** 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 root.search(word,0);
        }
        
        private class TrieNode {
            private final Map<Character,TrieNode> map = new HashMap<>();
            private boolean isEnd;
            void add(String s, int pos) {
                if(pos==s.length()) {
                    isEnd=true;
                    return;
                }
                
                TrieNode node = map.get(s.charAt(pos));
                if(node==null) {
                    node = new TrieNode();
                    map.put(s.charAt(pos),node);
                }
                node.add(s,pos+1);
            }
            
            boolean search(String s, int pos) {
                if(pos == s.length()) {
                    return isEnd;
                }
                
                char c = s.charAt(pos);
                if(c=='.') {
                    //dfs for all values.
                    for(TrieNode n : map.values()) {
                        if(n.search(s,pos+1)) {
                            return true;
                        }
                    }
                    return false;
                }
                TrieNode node = map.get(s.charAt(pos));
                if(node == null) {
                    return false;
                }
                
                return node.search(s,pos+1);
            }
        }
    }
    
    

Log in to reply
 

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