【原】610，实现 Trie (前缀树)

数据结构和算法 2023-06-10 发布于上海

展开全文

问题描述

来源：LeetCode第208题

难度：中等

Trie（发音类似"try"）或者说前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串word 。
boolean search(String word) 如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。
boolean startsWith(String prefix) 如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false 。

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True

提示：

1<=word.length, prefix.length<=2000
word和prefix仅由小写英文字母组成
insert、search和startsWith调用次数总计不超过3*10^4次

问题分析

Trie树也叫字典树，就像查字典一样，比如在字典中我们要找wo，第一步需要找到w，然后第2步再找o。其实我们可以把它看做是一棵n叉树，就是每个节点下面最多有n个子节点。题中说了word和prefix仅由小写英文字母组成，因为小写英文字母有26个，所以我们可以把它看做是一棵26叉树。如下图所示

他有一个根节点，根节点是不存储任何值的，然后根节点下面最多有26个子节点，每个子节点最多又有26个子节点……，比如字符串

“ac”，“bcd”，“ace”，“ef”

在字典树中是这样存在的

但是这里会有一个问题，我们没有储藏字符串“bc”，但上面字典树中包含字符串“bc”，其中还包括字符串“a”，“b”，“e”。实际上他们都不是一个完整的字符串，而是我们储藏字符串的前缀。那么怎么确定是否是一个完整的字符串中，我们需要对字符串的最后一个字符进行标记，如下图所示

如上图所示，因为字符串“bc”的最后一个字符“c”没有被标记，所以字符串“bc”不是一个完整的字符串。至于怎么标记大家可以自己定，这里我们通过一个boolean类标来标记，节点类如下

//创建节点类
class TrieNode {
    /**
     * 标记是否为完整字符串，如果是字符串的
     * 最后一个字符，则为true，否则为false。
     */
    boolean isWord;
    //26个子节点
    TrieNode[] children;

    public TrieNode() {
        isWord = false;
        children = new TrieNode[26];
    }
}

注意这里的节点类并没有存储单个字符，我们根据他是否为空来判断相对应的字符是否存在。比如我们查找字符a，因为a是26个节点中的第一个，我们只需要判断第一个子节点是否为空即可。如果为空表示a不存在，否则表示a存在，我们来看下完整代码

public class Trie {
    //根节点，根节点是不存储任何字母的，从根节点的
    //子节点开始存储
    private TrieNode root;

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

    //插入字符串
    public void insert(String word) {
        TrieNode parentNode = root;
        for (int i = 0; i < word.length(); i++) {
            //计算是父节点的哪个子节点
            int index = word.charAt(i) - 'a';
            //判断字符有没有创建，如果没有创建就创建
            if (parentNode.children[index] == null) {
                parentNode.children[index] = new TrieNode();
            }
            //更新父节点
            parentNode = parentNode.children[index];
        }
        //最后一个字符才能构成一个完整的单词
        parentNode.isWord = true;
    }

    //查找,判断是否是个完整的字符串
    public boolean search(String word) {
        TrieNode current = find(word);
        return current != null && current.isWord;
    }

    //是否以prefix为前缀
    public boolean startsWith(String prefix) {
        return find(prefix) != null;
    }

    //查找字典树中是否有str字符串
    private TrieNode find(String str) {
        TrieNode parentNode = root;
        int length = str.length();
        for (int i = 0; i < length; i++) {
            int index = str.charAt(i) - 'a';
            //只要有一个字符节点不存在就返回null
            if ((parentNode = parentNode.children[index]) == null)
                return null;
        }
        return parentNode;
    }
}