Topic source

208. Implement Trie (prefix tree)

Title details

Trie (pronounced like "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in string data sets. This data structure has many application scenarios, such as automatic completion and spell checking.

Please implement the Trie class:

• Trie() initializes the prefix tree object.
• void insert(String word) inserts the string word into the prefix tree.
• boolean search(String word) returns true if the string word is in the prefix tree (that is, it has been inserted before retrieval); Otherwise, false is returned.
• boolean startsWith(String prefix) returns true if one of the prefixes of the previously inserted string word is prefix; Otherwise, false is returned.

Example:

input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
output
[null, null, true, false, true, null, true]

explain
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // Return True
trie.search("app"); // Return False
trie.startsWith("app"); // Return True
trie.insert("app");
trie.search("app"); // Return True

Tips:

• 1 <= word.length, prefix.length <= 2000
• word and prefix are composed of lowercase English letters only
• The total number of insert, search and startsWith calls shall not exceed 3 * 104

Problem solving analysis

1. This problem requires us to implement a prefix tree ourselves. In fact, if we understand the principle of prefix tree, it is easier to implement it ourselves.
2. Since the prefix tree is a tree structure, you first need to define the TreeNode data structure, and how should the member variables be set? Considering the special structure of the prefix tree, each edge of the prefix tree has letters as signs, so it is necessary to set a TreeNode[] next as the adjacent node array, and the subscript of the array should be 26 English letters, which can also be regarded as adjacent edges. In addition, you need to set a boolean variable to identify whether a node is the end node of a character prefix.
3. According to the tree node structure we defined earlier, we can easily write the four methods required by the topic, especially the last three methods. Their implementation logic is similar, that is, they need to traverse each character of the string and find out whether there is a corresponding inserted character node or edge in the prefix tree.

class Trie {

    class TreeNode{
        boolean isEnd;// Is there a string that ends with this node
        TreeNode[] next; // The adjacent edge of the current node

        TreeNode(){
            isEnd = false;
            next = new TreeNode[26];// Characters are only composed of lowercase English letters, and a node has a maximum of 26 edges
        }
    }

    private TreeNode root;

    public Trie() {
        root = new TreeNode();
    }
    
    public void insert(String word) {
        TreeNode now = root;
        for(char ch : word.toCharArray()){
            if(now.next[ch - 'a'] == null){
                now.next[ch - 'a'] = new TreeNode();
            }
            now = now.next[ch - 'a'];
        }
        now.isEnd = true;
    }
    
    public boolean search(String word) {
        TreeNode now = root;
        for(char ch : word.toCharArray()){
            if(now.next[ch - 'a'] == null){
                return false;
            }
            now = now.next[ch - 'a'];
        }
        return now.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        TreeNode now = root;
        for(char ch : prefix.toCharArray()){
            if(now.next[ch - 'a'] == null){
                return false;
            }
            now = now.next[ch - 'a'];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

Result display