My simple Java solution


  • 0
    S
    class TrieNode {
        // Initialize your data structure here.
        char val;
        Set<TrieNode> next;
        public TrieNode() {
        }
        
        public TrieNode(char val) {
            this.val = val;
            this.next = new HashSet<>();
        }
    }
    
    public class Trie {
        private TrieNode root;
    
        public Trie() {
            root = new TrieNode('*');
        }
    
        // Inserts a word into the trie.
        public void insert(String word) {
            if (word == null || word.length() == 0) {
                return;
            }
            char[] chars = word.toCharArray();
            insertChars(chars, 0, root);
        }
    
        private void insertChars(char[] chars, int index, TrieNode node) {
            if (index == chars.length) {
                node.next.add(null);
                return;
            }
            boolean found = false;
            for (TrieNode n : node.next) {
                if (n != null && n.val == chars[index]) {
                    found = true;
                    insertChars(chars, ++index, n);
                    return;
                }
            }
            if (!found) {
                TrieNode newNode = new TrieNode(chars[index]);
                node.next.add(newNode);
                insertChars(chars, ++index, newNode);
            }
        }
        
        // Returns if the word is in the trie.
        public boolean search(String word) {
            char[] chars = word.toCharArray();
            return searchChars(chars, 0, root);
        }
        
    /* Method to recurse over each input character and terminating when the input is exhausted and it has a null as its children. This confirms that the search word is present in the tree. */
        private boolean searchChars(char[] chars, int index, TrieNode node) {
            if (index == chars.length && node.next.contains(null)) {
                return true;
            } else if (index == chars.length && !node.next.contains (null)) {
                return false;
            }
            for (TrieNode n : node.next) {
                if (n != null && n.val == chars[index]) {
                    return searchChars(chars, ++index, n);
                }
            }
            return false;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            char[] chars = prefix.toCharArray();
            return ifStartsWith(chars, 0, root);
        }
        
    /* Method to recurse over each input character and check if the TrieNode for that character is present */
        private boolean ifStartsWith(char[] chars, int index, TrieNode node) {
            if (index == chars.length) {
                return true;
            }
            for (TrieNode n : node.next) {
                if (n !=null && n.val == chars[index]) {
                    return ifStartsWith(chars, ++index, n);
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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