Java, using recursion, easy to understand


  • 0
    D
    public class Trie {
    
        // e.g if insert word "book", Node with 'k', the end field is set to be true
        class Node
        {
            boolean end;
            Node[] next;
            
            Node()
            {
                end = false;
                next = new Node[26];
            }
        }
        
        Node root;
        
        /** Initialize your data structure here. */
        public Trie() {
            root = new Node();
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) 
        {
         	insert(root, word.toCharArray(), 0);   
        }
        
        private void insert(Node n, char[] w, int id)
        {
            if (id == w.length) { n.end = true; return; }
                
            char c = w[id];
            if (n.next[c - 'a'] == null)
            {
                n.next[c - 'a'] = new Node();
            }
            
            insert(n.next[c - 'a'], w, id + 1);
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) 
        {
            return search(root, word.toCharArray(), 0);
        }
        
        private boolean search(Node n, char[] w, int id)
        {
            if (n == null) { return false; }
            if (id == w.length) { return n.end; }
            
            char c = w[id];
            return search(n.next[c - 'a'], w, id + 1);
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) 
        {
            return startsWith(root, prefix.toCharArray(), 0);
        }
        
        private boolean startsWith(Node n, char[] pre, int id)
        {
            if (n == null) { return false; }
            if (id == pre.length) { return true; }
            
            char c = pre[id];
            return startsWith(n.next[c - 'a'], pre, id + 1);
            
        }
    }
    

Log in to reply
 

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