How to implement prefix tree in Java

1. Prefix tree

1. What is a prefix tree

Dictionary tree (Trie tree) is a tree data structure that is often used for the storage and search of strings. The core idea of ​​the dictionary tree is to use common prefixes between strings to save storage space and improve query efficiency. It is a multi-tree, each node represents the prefix of a string, and the path from the root node to the leaf node constitutes a string.

The root node of the dictionary tree does not contain characters. Each child node represents a character. The characters on the path from the root node to any node are connected to the string represented by the node. Each node can store one or more strings, usually using a flag to mark whether the string represented by a node exists. When you need to find a string in a set of strings, you can use a dictionary tree to achieve efficient search operations.

2. Example of prefix tree

For example, create a prefix tree for the string array {"goog", "google", "bai", "baidu", "a"}. At this time We can clearly see some characteristics of the prefix tree:

• The root node does not store characters

• The prefix tree is a multi-fork Tree

• Each node of the prefix tree saves one character

• Strings with the same prefix are saved on the same path

• The end of the string also has an end mark on the prefix tree.

2. Implementation of the prefix tree

Question 208 on Likou is to implement the prefix tree: Likou

1. The data structure of the prefix tree

When writing code, I prefer to use hashing Tables are used to store node information, and some can also use arrays to store node information. They are essentially the same

public class Trie {
    Map<Character, Trie> next;
    boolean isEnd;
    public Trie() {
        this.next = new HashMap<>();
        this.isEnd = false;
    }
    public void insert(String word) {
    }
    public boolean search(String word) {
        return false;
    }
    public boolean startsWith(String prefix) {
        return false;
    }
}

2. Insert string

    public void insert(String word) {
        Trie trie = this;//获得根结点
        for (char c : word.toCharArray()) {
            if (trie.next.get(c) == null) {//当前结点不存在
                trie.next.put(c, new Trie());//创建当前结点
            }
            trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
        }
        trie.isEnd = true;
    }

3. Find characters String

    public boolean search(String word) {
        Trie trie = this;//获得根结点
        for (char c : word.toCharArray()) {
            if (trie.next.get(c) == null) {//当前结点不存在
                return false;
            }
            trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
        }
        return trie.isEnd;
    }

4. Find the prefix

    public boolean startsWith(String prefix) {
        Trie trie = this;//获得根结点
        for (char c : prefix.toCharArray()) {
            if (trie.next.get(c) == null) {//当前结点不存在
                return false;
            }
            trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
        }
        return true;
    }

The next step is to answer some questions about the prefix tree

3. The longest word in the dictionary

1. Question description

Given an English dictionary composed of a string array words. Returns the longest word in words, which is formed by gradually adding one letter to other words in the words dictionary.

If there are multiple feasible answers, return the word with the smallest lexicographic order among the answers. If there is no answer, an empty string is returned.

Likou: Likou

2. Problem analysis

This is a typical prefix tree question, but this question has some special requirements and the returned answer It is:

1. The longest word

2. This word is gradually composed of other words

3. The same length returns the smallest word in lexicographic order

Therefore, we need to modify the relevant code of the prefix tree. The code for inserting strings one by one remains unchanged. The main modification is the search code. We should add a judgment in trie.next.get(c) == null The condition for false is that each node should have a flag true, indicating that there is a word in each node, and finally the longest word (the word of the leaf node) is formed step by step

3. Code Implement

class Solution {
    public String longestWord(String[] words) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        String longest = "";
        for (String word : words) {
            if (trie.search(word)) {
                if (word.length() > longest.length() || ((word.length() == longest.length()) && (word.compareTo(longest) < 0))) {
                    longest = word;
                }
            }
        }
        return longest;
    }
}
class Trie {
    Map<Character, Trie> next;
    boolean isEnd;
    public Trie() {
        this.next = new HashMap<>();
        this.isEnd = false;
    }
    public void insert(String word) {
        Trie trie = this;//获得根结点
        for (char c : word.toCharArray()) {
            if (trie.next.get(c) == null) {//当前结点不存在
                trie.next.put(c, new Trie());//创建当前结点
            }
            trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
        }
        trie.isEnd = true;
    }
    public boolean search(String word) {
        Trie trie = this;//获得根结点
        for (char c : word.toCharArray()) {
            if (trie.next.get(c) == null || !trie.next.get(c).isEnd) {//当前结点不存在
                return false;
            }
            trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
        }
        return trie.isEnd;
    }
}

The above is the detailed content of How to implement prefix tree in Java. For more information, please follow other related articles on the PHP Chinese website!