AC solution in Java


  • 19
    L
    class TrieNode {
        private final int R = 26;
        private final TrieNode[] children;
        private String item;
        
        public TrieNode() {
            children = new TrieNode[R];
            item = "";
        }
        
        public String getItem() {
            return item;
        }
        
        public void setItem(String item) {
            this.item = item;
        }
        
        public TrieNode[] getChildren() {
            return children;
        }
        
        public TrieNode getChild(int i) {
            if (i >= 26 || i < 0) throw new IllegalArgumentException();
            return children[i];
        }
        
        public void setChild(int i, TrieNode node) {
            children[i] = node;
        }
    }
    
    public class Trie {
        private TrieNode root;
    
        public Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        public void insert(String word) {
            TrieNode curr = root;
            for (char c : word.toCharArray()) {
                if (curr.getChild(c - 'a') == null) curr.setChild(c - 'a', new TrieNode());
                curr = curr.getChild(c - 'a');
            }
            curr.setItem(word);
        }
    
        // Returns if the word is in the trie.
        public boolean search(String word) {
            TrieNode curr = root;
            for (char c : word.toCharArray()) {
                if (curr.getChild(c - 'a') == null) return false;
                curr = curr.getChild(c - 'a');
            }
            return curr.getItem().equals(word);
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            TrieNode curr = root;
            for (char c : prefix.toCharArray()) {
                if (curr.getChild(c - 'a') == null) return false;
                curr = curr.getChild(c - 'a');
            }
            return true;
        }
    }
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie = new Trie();
    // trie.insert("somestring");
    // trie.search("key");
    

    This is standard trie data structure implementation. It is a bit longer since I used getter and setter for TrieNode class.


  • 0
    A

    Very good implementation thank for that,.


  • 23
    Z

    You don't actually need to store the whole string in each node, a boolean flag is sufficient to indicate that the node has completed one word. This solution saves space when lots of words share the same prefix.

    class TrieNode {
        boolean isEndOfWord;
        TrieNode[] children;
        
        // Initialize your data structure here.
        public TrieNode() {
            this.isEndOfWord = false;
            this.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 runner = root;
            for(char c : word.toCharArray()){
                if(runner.children[c-'a'] == null) {
                    runner.children[c-'a'] = new TrieNode();
                }
                runner = runner.children[c-'a'];
            }
            runner.isEndOfWord = true;
        }
    
        // Returns if the word is in the trie.
        public boolean search(String word) {
            TrieNode runner = root;
            for(char c : word.toCharArray()) {
                if(runner.children[c-'a'] == null) {
                    return false;
                } else {
                    runner = runner.children[c-'a'];
                }
            }
            return runner.isEndOfWord;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            TrieNode runner = root;
            for(char c : prefix.toCharArray()) {
                if(runner.children[c-'a'] == null) {
                    return false;
                } else {
                    runner = runner.children[c-'a'];
                }
            }
            return true;
        }
    }
    

  • 0
    L

    Thank you for your comment. I know I do not have to, just like I do not have to write the getters and setters. The reason I used a item object is that in this way, it can be easily extended to symbols table where the item object is a generic type associated with a string key.


  • 0
    R

    Great solution! Thanks for the insight.


  • 0
    S

    MO BAI DA SHEN


  • 0
    R

    @zheng Elegant code!


  • 0
    H

    2 possible optimizations:

    1. use a space to store int offset = c - 'a' can avoid some calculation.
    2. the get() and set() method are good practice in our work. but seem not necessary here ^^

  • 0
    A

    Can someone please extend this code to show all words that can be obtained from a prefix?


Log in to reply
 

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