An extremely simple Java solution


  • 0
    L
    public class Trie {
        final private TrieNode root = new TrieNode();
        
        /** Initialize your data structure here. */
        public Trie() {
            
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) {
            root.insert(word,0);
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            return root.search(word,0);
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            return root.startsWith(prefix,0);
        }
        
        private class TrieNode {
            private boolean isEndOfWord;
            private final Map<Character,TrieNode> nodes = new HashMap<>();
            
            private void insert(String word,int i) {
                if(i==word.length()) {
                    isEndOfWord=true;
                    return;
                }
                char c = word.charAt(i);
                TrieNode child = nodes.get(c);
                if(child==null) {
                    child = new TrieNode();
                    nodes.put(c,child);
                }
                child.insert(word,i+1);
            }
            
            private boolean search(String word,int i) {
                if(word.length()==i) {
                    return isEndOfWord;
                }
                char c = word.charAt(i);
                TrieNode child = nodes.get(c);
                if(child==null) {
                    return false;
                }
                return child.search(word,i+1);
            }
            
            private boolean startsWith(String prefix,int i) {
                if(prefix.length()==i) {
                    return true;
                }
                char c = prefix.charAt(i);
                TrieNode child = nodes.get(c);
                if(child==null) {
                    return false;
                }
                return child.startsWith(prefix,i+1);            
            }        
            
            /**
             * Returns true if it is the end of the Trie.
             */
            private boolean isEnd() {
                return isEndOfWord;
            }
        }
    }
    

Log in to reply
 

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