Question

Formatted question description: https://leetcode.ca/all/208.html

208	Implement Trie (Prefix Tree)

Implement a trie with methods
    insert
    search
    startsWith

Note:
You may assume that all inputs are consist of lowercase letters a-z.

@tag-trie

Algorithm

Each node of the alphabetic dictionary tree defines an array of child node pointers with a size of 26, and then uses a marker to record whether it is a word up to the current position.

When initializing, the 26 child nodes are all empty.

Then the insert operation only needs to calculate the position of each character of the string to be inserted, and then find out whether this child node exists, if it does not exist, create a new one, and then move to the next one.

The word search and prefix search operations are very similar to the insert operation. The difference is that if there are no child nodes, false is returned. At the end of the search time, you need to look at the flag, and you can directly return true when you search the prefix.

Code

Java

public class Implement_Trie_Prefix_Tree {

    public static void main(String[] args) {
        Implement_Trie_Prefix_Tree out = new Implement_Trie_Prefix_Tree();

        Trie trie = out.new Trie();
        trie.insert("abc");
        trie.insert("ab");
        System.out.println(trie.search("ab"));
        trie.insert("ab");
        System.out.println(trie.search("ab"));
        System.out.println(trie.startsWith("a"));

    }

    class TrieNode {

        // R children to node children
        private TrieNode[] children;

        private final int R = 26;

        private boolean isEnd;

        public TrieNode() {
            children = new TrieNode[R];
        }

        public boolean containsKey(char ch) {
            return children[ch - 'a'] != null;
        }

        public TrieNode get(char ch) {
            return children[ch - 'a'];
        }

        public void put(char ch, TrieNode node) {
            children[ch - 'a'] = node;
        }

        public void setEnd() {
            isEnd = true;
        }

        public boolean isEnd() {
            return isEnd;
        }
    }

    class Trie {
        private TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        // Inserts a word into the trie.
        public void insert(String word) {
            TrieNode node = root;

            // @note:@memorize: iteration is better than recursion during trie building
            for (int i = 0; i < word.length(); i++) {
                char currentChar = word.charAt(i);
                if (!node.containsKey(currentChar)) {
                    node.put(currentChar, new TrieNode());
                }
                node = node.get(currentChar);
            }
            node.setEnd();
        }

        // search a prefix or whole key in trie and
        // returns the node where search ends
        private TrieNode searchPrefix(String word) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                char curLetter = word.charAt(i);
                if (node.containsKey(curLetter)) {
                    node = node.get(curLetter);
                } else {
                    return null;
                }
            }
            return node;
        }

        // Returns if the word is in the trie.
        public boolean search(String word) {
            TrieNode node = searchPrefix(word);
            return node != null && node.isEnd();
        }

        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            TrieNode node = searchPrefix(prefix);
            return node != null;
        }
    }

    // Your Trie object will be instantiated and called as such:
    // Trie trie = new Trie();
    // trie.insert("somestring");
    // trie.search("key");

}

208 - Implement Trie (Prefix Tree)

Question

Algorithm

Code

All Problems

All Solutions