Java - O(d) with HashMap


  • 0
    C
    class TrieNode {
        private char letter;
        private Map<Character, TrieNode> children;
        
        // Initialize your data structure here.
        public TrieNode() {
            children = new HashMap<Character, TrieNode>();
        }
        
        public TrieNode(char letter) {
            this.letter = letter;
            children = new HashMap<Character, TrieNode>();
        }
        
        public char getLetter() {
            return this.letter;
        }
        
        public Map<Character, TrieNode> getChildren() {
            return this.children;
        }
    }
    
    public class Trie {
        private TrieNode root;
    
        public Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        public void insert(String word) {
            insert(root, word);
        }
        
        private void insert(TrieNode node, String word) {
            if(word.isEmpty()) {
                node.getChildren().put(null, new TrieNode());
                return;
            }
            
            Map<Character, TrieNode> children = node.getChildren();
            char ch = word.charAt(0);
            
            TrieNode matched = children.get(ch);
            
            if(matched == null) {
                matched = new TrieNode(ch);
                children.put(ch, matched);
            }
            
            insert(matched, word.substring(1));
        }
    
        // Returns if the word is in the trie.
        public boolean search(String word) {
            return searchPath(root, word, true);
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            return searchPath(root, prefix, false);
        }
        
        private boolean searchPath(TrieNode sNode, String word, boolean complete) {
            if(word.isEmpty()) {
                return !complete || sNode.getChildren().containsKey(null);
            }
            
            TrieNode matched = sNode.getChildren().get(word.charAt(0));
            
            if(matched == null) {
                return false;
            }
            
            return searchPath(matched, word.substring(1), complete);
        }
    }
    

    Time complexity: O(d) --> d is the height of the tree.


Log in to reply
 

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