208. Implement Trie (Prefix Tree)

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

A Trie (pronounced like “try”) or prefix tree is a tree data structure for efficiently storing and retrieving keys in a string data set. This data structure has a number of applications, such as auto-completion and spell checking.

Please implement 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, inserted before retrieval); Otherwise, return false.
Boolean startsWith(String prefix) Returns true if one of the prefixes of the previously inserted String word is prefix; Otherwise, return false.

Example: Enter ["Trie"."insert"."search"."search"."startsWith"."insert"."search"[[]], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"[]] outputnull.null, true, false, true, null, true] 解 决 Trie Trie = new Trie(); trie.insert("apple");
trie.search("apple");   / / return True
trie.search("app");     / / returns False
trie.startsWith("app"); / / return True
trie.insert("app");
trie.search("app");     / / return True
Copy the code

Tip:

1 <= word.length, prefix.length <= 2000
Word and prefix are lowercase letters only

Their thinking

The core data structure of the dictionary tree is a multi-fork tree. We can determine whether there is a string whose value at the ith position is (char) (j+’a’) according to whether the JTH node of the ith layer is empty. Through such a tree, we can quickly determine whether our input string exists in the existing string

code

class Trie {

    Node root =new Node();
    /** Initialize your data structure here. */
    public Trie(a) {}/** Inserts a word into the trie. */
    public void insert(String word) {
        Node cur=root;
        for(int i=0; i<word.length(); i++) {if(cur.nodes[word.charAt(i)-'a'] = =null)    
             cur.nodes[word.charAt(i)-'a'] =new Node();
             cur=cur.nodes[word.charAt(i)-'a'];
        }
        cur.isEnd=true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {

        Node cur=root;
        for(int i=0; i<word.length(); i++) {if(cur.nodes[word.charAt(i)-'a']! =null)
                cur=cur.nodes[word.charAt(i)-'a'];
            else return false;
        }
        return cur.isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String word) {
        Node cur=root;
        for(int i=0; i<word.length(); i++) {if(cur.nodes[word.charAt(i)-'a']! =null)
                cur=cur.nodes[word.charAt(i)-'a'];
            else return false;
        }
        return true; }}class Node{
        Node[] nodes;
        boolean isEnd=false;
        public Node(a){
            nodes=new Node[26]; }}/** * 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); * /
Copy the code

208. Implement Trie (Prefix Tree)