current position:Home>Leetcode's skill of writing questions -- dictionary tree

Leetcode's skill of writing questions -- dictionary tree

2022-02-03 16:17:35 Glimmer

1. Dictionary tree

Trie Trees , Dictionary tree , Also known as word search tree or key tree , It's a tree structure , It's a variation of the hash tree .

A typical application is to count and sort a large number of strings ( But it's not just about strings ), So it is often used in text word frequency statistics by search engine system .

Trie The core idea is space for time . It minimizes unnecessary string comparisons , Using the common prefix of string to reduce the overhead of query time , Query efficiency is higher than hash tree .

2. The nature of the dictionary tree

image.png

  1. Except for the root node , Each node contains only one character
  2. All children of each node contain different characters
  3. From the root node to a node , Connect the characters on the path , Is the string corresponding to the node

3. Dictionary tree instance

(1) Construct a dictionary tree

public class Trie {
    /**
     *  The node of the dictionary tree 
     */
    static class TrieNode {
        //  Represents the value of the current node 
        char value;

        //  Indicates whether the current node is a terminating node ( This is not a leaf node , It means whether it is the end of the word )
        boolean flag;

        //  An array representing the children of the current node , Regardless of case, there are 26 Letters , So the initialization size is 26
        TrieNode[] nextNodes = new TrieNode[26];

        public TrieNode() {
        }

        public TrieNode(char value) {
            this.value = value;
        }
    }

    /**
     *  Insert a new word 
     *
     * @param root  The root node 
     * @param str  New word to insert 
     */
    public void insert(TrieNode root, String str) {
        if (root == null || str == null || str.length() == 0) {
            return;
        }
        for (int i = 0; i < str.length(); i++) {
            // index Indicates the position of the current character in the character table 
            int index = str.charAt(i) - 'a';
            //  If the branch does not exist , Then create a new node 
            if (root.nextNodes[index] == null) {
                root.nextNodes[index] = new TrieNode(str.charAt(i));
            }
            //  Assign this node to root, Go to the next level of the tree 
            root = root.nextNodes[index];
        }
        //  Set the current node as the termination node 
        root.flag = true;
    }
}
 Copy code 

(2) Find out if the word exists in the dictionary tree

    /**
     *  Find out if a word exists 
     *
     * @param root  The root node 
     * @param str  The word to look for 
     */
    public boolean search(TrieNode root, String str) {
        if (root == null || str == null || str.length() == 0) {
            return false;
        }
        for (int i = 0; i < str.length(); i++) {
            // index Represents the position of the current character in the character table in 
            int index = str.charAt(i) - 'a';
            //  If the branch does not exist , The character does not exist 
            if (root.nextNodes[index] == null) {
                return false;
            }
            //  Assign the current node to root, Go to the next level of the tree 
            root = root.nextNodes[index];
        }
        //  If the current node is a termination node , It means that there is , Otherwise, it doesn't exist 
        return root.flag;
    }
 Copy code 

4. Leetcode The real question

Leetcode Upper part 208 The problem is to implement a prefix tree , Dictionary tree .

image.png

The meaning of the question is very simple and rough , Four of these methods need to be implemented :
I won't say much about the construction method .
insert Methods and search Methods can use the above code almost intact , But one thing to note is , Because the example of the topic will call the method continuously , After each execution of the method , In fact, it has changed root References to , There will be problems with subsequent method calls . Here you can use another reference , To save the root node .
To achieve startWith Method , Only need to search Slightly change the method , Then extract a method from the repeated code .

public class Trie {
    //  Save the root node 
    TrieNode root;
    //  Save the current node 
    TrieNode curr;

    /**
     *  The node of the dictionary tree 
     */
    static class TrieNode {
        //  Represents the value of the current node 
        char value;

        //  Indicates whether the current node is a terminating node ( This is not a leaf node , It means whether it is the end of the word )
        boolean flag;

        //  An array representing the children of the current node , The title description has only lowercase letters , So the initialization size is 26
        TrieNode[] nextNodes = new TrieNode[26];

        public TrieNode() {
        }

        public TrieNode(char value) {
            this.value = value;
        }
    }


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

    public void insert(String word) {
        curr = root;
        if (curr == null || word == null || word.length() == 0) {
            return;
        }
        for (int i = 0; i < word.length(); i++) {
            // index Indicates the position of the current character in the character table 
            int index = word.charAt(i) - 'a';
            //  If the branch does not exist , Then create a new node 
            if (curr.nextNodes[index] == null) {
                curr.nextNodes[index] = new TrieNode(word.charAt(i));
            }
            //  Assign this node to root, Go to the next level of the tree 
            curr = curr.nextNodes[index];
        }
        //  Set the current node as the termination node 
        curr.flag = true;
    }

    public boolean search(String word) {
        if (searchPrefix(word)) return false;
        //  If the current node is a termination node , It means that there is , Otherwise, it doesn't exist 
        return curr.flag;
    }

    public boolean startsWith(String prefix) {
        //  Whether the current node is a terminating node or not , All back to true
        return !searchPrefix(prefix);
    }

    private boolean searchPrefix(String prefix) {
        curr = root;
        if (curr == null || prefix == null || prefix.length() == 0) {
            return true;
        }
        for (int i = 0; i < prefix.length(); i++) {
            // index Represents the position of the current character in the character table in 
            int index = prefix.charAt(i) - 'a';
            //  If the branch does not exist , The character does not exist 
            if (curr.nextNodes[index] == null) {
                return true;
            }
            //  Assign the current node to root, Go to the next level of the tree 
            curr = curr.nextNodes[index];
        }
        return false;
    }
}
 Copy code 

TrieNode In fact, you do not need to save the value of the current node , Because its value can actually be calculated through its index , In fact, what we compare is the index , Not its value .
in fact , In fact, even the statement TrieNode There is no need to , If you are interested, you can try .

Reference

Leetcode:leetcode-cn.com/problems/im…

copyright notice
author[Glimmer],Please bring the original link to reprint, thank you.
https://en.fheadline.com/2022/02/202202031617331943.html

Random recommended