Share my Java Solution


  • 0
    P
    class TrieNode {
        // Initialize your data structure here.
        char key;
        boolean isWord;
        List<TrieNode> children;
        
        public TrieNode() {
            children = new ArrayList<TrieNode>();
        }
        
        public TrieNode(char key, boolean isWord) {
            this();
            this.key = key;
            this.isWord = isWord;
        }
    }
    
    public class Trie {
        private TrieNode root;
    
        public Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        public void insert(String word) {
            for(TrieNode child : root.children)
                if(insert(child, word, 0))
                    return;
            root.children.add(createNode(word, 0));
        }
        
        private boolean insert(TrieNode node, String word, int index) {
            if(node.key != word.charAt(index))
                return false;
            if(index == word.length() - 1) {
                node.isWord = true;
                return true;
            }
            for(TrieNode child : node.children)
                if(insert(child, word, index + 1))
                    return true;
            node.children.add(createNode(word, index + 1));
            return true;
        }
        
        private TrieNode createNode(String word, int index) {
            boolean isWord = index == word.length() - 1;
            TrieNode newNode = new TrieNode(word.charAt(index), isWord);
            if(!isWord)
                newNode.children.add(createNode(word, index + 1));
            return newNode;
        }
    
        // Returns if the word is in the trie.
        public boolean search(String word) {
            for(TrieNode child : root.children)
                if(search(child, word, 0))
                    return true;
            return false;
        }
        
        private boolean search(TrieNode node, String word, int index) {
            if(node.key != word.charAt(index))
                return false;
            if(index == word.length() - 1) {
                if(node.isWord)
                    return true;
                else
                    return false;
            } else {
                for(TrieNode child : node.children)
                    if(search(child, word, index + 1))
                        return true;
                return false;
            }
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            for(TrieNode child : root.children)
                if(startsWith(child, prefix, 0))
                    return true;
            return false;
        }
        
        private boolean startsWith(TrieNode node, String prefix, int index) {
            if(node.key != prefix.charAt(index))
                return false;
            if(index == prefix.length() - 1) {
                return true;
            } else {
                for(TrieNode child : node.children)
                    if(startsWith(child, prefix, index + 1))
                        return true;
                return false;
            }
        }
    }

Log in to reply
 

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