AC JAVA solution simple using single array


  • 84

    Detailed explanation after code!

    class TrieNode {
        public char val;
        public boolean isWord; 
        public TrieNode[] children = new TrieNode[26];
        public TrieNode() {}
        TrieNode(char c){
            TrieNode node = new TrieNode();
            node.val = c;
        }
    }
    
    public class Trie {
        private TrieNode root;
        public Trie() {
            root = new TrieNode();
            root.val = ' ';
        }
    
        public void insert(String word) {
            TrieNode ws = root;
            for(int i = 0; i < word.length(); i++){
                char c = word.charAt(i);
                if(ws.children[c - 'a'] == null){
                    ws.children[c - 'a'] = new TrieNode(c);
                }
                ws = ws.children[c - 'a'];
            }
            ws.isWord = true;
        }
    
        public boolean search(String word) {
            TrieNode ws = root; 
            for(int i = 0; i < word.length(); i++){
                char c = word.charAt(i);
                if(ws.children[c - 'a'] == null) return false;
                ws = ws.children[c - 'a'];
            }
            return ws.isWord;
        }
    
        public boolean startsWith(String prefix) {
            TrieNode ws = root; 
            for(int i = 0; i < prefix.length(); i++){
                char c = prefix.charAt(i);
                if(ws.children[c - 'a'] == null) return false;
                ws = ws.children[c - 'a'];
            }
            return true;
        }
    }
    

    With my solution I took the simple approach of giving each TrieNode a 26 element array of each possible child node it may have. I only gave 26 children nodes because we are only working with lowercase 'a' - 'z'. If you are uncertain why I made the root of my Trie an empty character this is a standard/typical approach for building out a Trie it is somewhat arbitrary what the root node is.

    For insert I used the following algorithm. Loop through each character in the word being inserted check if the character is a child node of the current TrieNode i.e. check if the array has a populated value in the index of this character. If the current character ISN'T a child node of my current node add this character representation to the corresponding index location then set current node equal to the child that was added. However if the current character IS a child of the current node only set current node equal to the child. After evaluating the entire String the Node we left off on is marked as a word this allows our Trie to know which words exist in our "dictionary"

    For search I simply navigate through the Trie if I discover the current character isn't in the Trie I return false.
    After checking each Char in the String I check to see if the Node I left off on was marked as a word returning the result.

    Starts with is identical to search except it doesn't matter if the Node I left off was marked as a word or not if entire string evaluated i always return true;


  • 122
    A

    There is some code that is redundant in your solution. Below is accepted as well:

    class TrieNode {
        public boolean isWord; 
        public TrieNode[] children = new TrieNode[26];
        public TrieNode() {}
    }
    
    public class Trie {
        private TrieNode root;
        public Trie() {
            root = new TrieNode();
        }
    
        public void insert(String word) {
            TrieNode ws = root;
            for(int i = 0; i < word.length(); i++){
                char c = word.charAt(i);
                if(ws.children[c - 'a'] == null){
                    ws.children[c - 'a'] = new TrieNode();
                }
                ws = ws.children[c - 'a'];
            }
            ws.isWord = true;
        }
    
        public boolean search(String word) {
            TrieNode ws = root; 
            for(int i = 0; i < word.length(); i++){
                char c = word.charAt(i);
                if(ws.children[c - 'a'] == null) return false;
                ws = ws.children[c - 'a'];
            }
            return ws.isWord;
        }
    
        public boolean startsWith(String prefix) {
            TrieNode ws = root; 
            for(int i = 0; i < prefix.length(); i++){
                char c = prefix.charAt(i);
                if(ws.children[c - 'a'] == null) return false;
                ws = ws.children[c - 'a'];
            }
            return true;
        }
    }

  • 1
    X

    C++ complete object oriented version of the same thing

    class TrieNode {
    private: 
        vector<TrieNode *> children;
        bool anEnd;
    public:
        // Initialize your data structure here.
        TrieNode(): children(26, NULL), anEnd(false){}
        
        void addChild(char c, TrieNode* node){ children[c - 'a'] = node;}
        void setEnd(){ anEnd = true; }
        bool isAnEnd(){ return anEnd;}
        
        TrieNode * getChild(char c){
            if( children[c - 'a'] ) 
                return children[c - 'a'];
            else
                return NULL;
        }
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
        
        ~Trie() {
            remove(root);
        }
        
        void remove(TrieNode * node){
            for(int i = 0; i < 26; i++){
                if(node->getChild('a' + i))
                    remove(node->getChild('a' + i));
            }
            delete node;
        }
    
        // Inserts a word into the trie.
        void insert(string word) {
            TrieNode * node = root;
            for(int i = 0; i < word.size(); i++){
                if(node->getChild(word[i]))
                    node = node->getChild(word[i]);
                else{
                    node->addChild(word[i], new TrieNode());
                    node = node->getChild(word[i]);
                }
            }
            node->setEnd();
        }
    
        // Returns if the word is in the trie.
        bool search(string word) {
            TrieNode * node = root;
            for(int i = 0; i < word.size(); i++){
                if(node->getChild(word[i]))
                    node = node = node->getChild(word[i]);
                else return false;
            }
            return node->isAnEnd();
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            TrieNode * node = root;
            for(int i = 0; i < prefix.size(); i++){
                if(node->getChild(prefix[i]))
                    node = node = node->getChild(prefix[i]);
                else return false;
            }
            return true;
        }
    
    private:
        TrieNode* root;
    };
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie;
    // trie.insert("somestring");
    // trie.search("key");

  • 1
    E

    If you want to reduce redundant code, you can safely combine search and startsWith into one helper function to reduce coding :) Check my solution here.


  • 3
    N

    Reduce redundant code again. Below is accepted too, 2333:

    class TrieNode {
        public boolean isWord;
        public TrieNode[] children = new TrieNode[26];
        // Initialize your data structure here.
        public TrieNode() {
            
        }
    }
    
    public class Trie {
        private TrieNode root;
    
        public Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        public void insert(String word) {
            TrieNode ws = root;
            for(int i = 0; i < word.length(); i++){
                char ch = word.charAt(i);
                if(ws.children[ch - 'a'] == null){
                    ws.children[ch - 'a'] = new TrieNode();
                }
                ws = ws.children[ch - 'a'];
            }
            ws.isWord = true;
        }
    
        // Returns if the word is in the trie.
        public boolean search(String word) {
            TrieNode ws = searchHelper(word);
            return ws != null && ws.isWord;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
             return searchHelper(prefix) != null;
        }
        
        public TrieNode searchHelper(String key){
            TrieNode ws = root;
            for(int i = 0; i < key.length() && ws != null; i++){
                char ch = key.charAt(i);
                ws = ws.children[ch - 'a'];
            }
            return ws;
        }
    }
    

  • 3
    J

    No need to store character in each node


  • 0
    D

    @JeremyLi28 How to implement?


  • 0
    D

    @noobsky good solution , never write same code twice.


  • 0
    J

    @D.Q.Zhang For example, it the child 'a' of a node is not null, then this child represent character 'a', no need to store 'a' again in this child node


  • 3
    C

    @mlblount45

    Concise Java solution avoiding duplicate code between 'search' and 'startsWith' functions:

    class TrieNode {
        // Initialize your data structure here.
    	TrieNode[] children;
    	String item;
    	
        public TrieNode() {
            children = new TrieNode[26];
            item = "";
        }
    }
    
    public class Trie {
        private TrieNode root;
    
        public Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        public void insert(String word) {
            TrieNode node = root;
            
            for(char ch: word.toCharArray()){
                int index = ch - 'a';
                if(node.children[index] == null) node.children[index] = new TrieNode();
                node = node.children[index];
            }
            
            node.item = word;
        }
    
        // Returns if the word is in the trie.
        public boolean search(String word) {
            return match(root, word, 0, false);
        }
        
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            return match(root, prefix, 0, true);
        }
        
        private boolean match(TrieNode node, String word, int i, boolean searchPrefix){
            if(node==null) return false;
            if(i==word.length()){
                if(searchPrefix) return true;
                return node.item.equals(word);
            }
            
            int index = word.charAt(i)-'a';
            return match(node.children[index], word, i+1, searchPrefix);
        }
    }
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie = new Trie();
    // trie.insert("somestring");
    // trie.search("key");
    

  • 0
    L

    @mlblount45 Your solution is good. Yet as mentioned below, some code is duplicate.

    A cleaner code can be found below.

    https://discuss.leetcode.com/topic/13463/maybe-the-code-is-not-too-much-by-using-next-26-c/2


  • 0

    @coderatleet

    I like this one. It is quite smart to store the entire word only at the "last" node of that word. Very concise and clear work. Good job.


  • 1
    C

    @Nakanu Thank you :)


  • 0
    S

    I think there is no need to store "public char val" in TrieNode since we don't use it.


  • 0
    K

    Hi,

    Thank you so much for posting your solutions here.
    I'm quite new here. May I ask what does AC stand for in AC JAVA solution?

    Thanks.


  • 0
    T

    @keweishang I believe it's accepted


  • 0

    I believe my code is cleaner

    class TrieNode {
        public boolean isWord; 
        public TrieNode[] children = new TrieNode[26];
    }
    
    public class Trie {
        private TrieNode root;
        
        
        public Trie() {
            root = new TrieNode();
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) {
            TrieNode cur = root;
            for(int i = 0; i < word.length(); i++){
                char c = word.charAt(i);
                if(cur.children[c - 'a'] == null){
                    cur.children[c - 'a'] = new TrieNode();
                }
                cur = cur.children[c - 'a'];
            }
            cur.isWord = true;
            
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            TrieNode cur = root;
            for(int i = 0; i < word.length(); i++){
                char c = word.charAt(i);
                if(cur.children[c - 'a'] == null)
                    return false;
                else cur = cur.children[c - 'a'];
            }
            return cur.isWord;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            TrieNode cur = root;
            for(int i = 0; i < prefix.length(); i++){
                char c = prefix.charAt(i);
                if(cur.children[c - 'a'] == null)
                    return false;
                else cur = cur.children[c - 'a'];
            }
            return true;
        }
    }
    
    

  • 0

    no need to explicitly write the construction function for TrieNode


  • 0
    F
    This post is deleted!

  • 0

    Here is my solution, hope can helps:

    class TrieNode{
        TrieNode[] next = new TrieNode[26];
        String word;
    }
    public class Trie {
        TrieNode root;
        /** Initialize your data structure here. */
        public Trie() {
            root = new TrieNode();
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) {
            TrieNode tree = root;
            for(char c : word.toCharArray()){
                if(tree.next[c-'a'] == null){
                    tree.next[c-'a'] = new TrieNode();
                }
                tree = tree.next[c-'a'];
            }
            tree.word = word;
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            TrieNode tree = root;
            for(char c : word.toCharArray()){
                if(tree.next[c-'a'] == null){
                    return false;
                }
                tree = tree.next[c-'a'];
            }
            if(tree.word == null){
                return false;
            }
            return tree.word.equals(word);
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            TrieNode tree = root;
            for(char c : prefix.toCharArray()){
                if(tree.next[c-'a'] == null){
                    return false;
                }
                tree = tree.next[c-'a'];
            }
            return true;
        }
    }
    

Log in to reply
 

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