Very Simple and Clear Java Solution.


  • 0

    There are a lot of solutions but not concise. Here I give a clear solution.

    • TrieNode only has two params which is childrens array and hasword. Childrens uses Char as index to store at current position. hasword to mark here is the end of a word.
    /** Initialize your data structure here. */
        public class TrieNode {
            public TrieNode[] childrens;
            public boolean hasword;
            public TrieNode () {
                childrens = new TrieNode[26];
                hasword = false;
            }
        }
    
        private TrieNode root;
        public Trie() {
           root = new TrieNode();
        }
    
        /** Inserts a word into the trie. */
        public void insert(String word) {
            TrieNode temp = root;
            
            for (int i = 0; i < word.length(); i++) {
                    char c = word.charAt(i);
                    if (temp.childrens[c - 'a'] == null) {
                         temp.childrens[c - 'a'] = new TrieNode();
                    } 
                    temp = temp.childrens[c - 'a'];
            }
            temp.hasword = true;
            
        }
    
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            TrieNode temp = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (temp.childrens[c - 'a'] == null) {
                    return false;
                } 
                temp = temp.childrens[c - 'a'];
                
            }
            return temp.hasword;
        }
    
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            TrieNode temp = root;
            for (int i = 0; i < prefix.length(); i++) {
                char c = prefix.charAt(i);
                if (temp.childrens[c - 'a']  == null) {
                    return false;
                }
                temp = temp.childrens[c - 'a'];
            }
            return true;
        }
    

Log in to reply
 

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