208. 实现 Trie (前缀树)

208. 实现 Trie (前缀树)

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

请你实现 Trie 类:

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


public class Trie {

    bool isEnd;
    Trie[] children = new Trie[26];

    public Trie() 
    {

    }
    
    public void Insert(string word) 
    {
        Trie temp = this;
        foreach(char c in word)
        {
            temp.children[c - 'a'] ??= new Trie();
            //??=是一个特殊的操作符
            //判断左侧的值是否为null
            //如果不是就返回左侧的值
            //如果是就返回右侧的值
            temp = temp.children[c - 'a'];
        }
        temp.isEnd = true;
    }
    
    public bool Search(string word) 
    {
        Trie temp = this;
        foreach(char c in word)
        {
            if(temp.children[c-'a'] == null)
            {
                return false;
            } 
            temp = temp.children[c-'a'];
        }
        return temp.isEnd;
    }
    
    public bool StartsWith(string prefix)
    {
        Trie temp = this;
        foreach(char c in prefix)
        {
            if(temp.children[c-'a'] == null)
            {
                return false;
            }
            temp = temp.children[c-'a'];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.Insert(word);
 * bool param_2 = obj.Search(word);
 * bool param_3 = obj.StartsWith(prefix);
 */

前缀树 又叫做字典树

如果不是每日一题恰好做到了我可能都不会看一眼这个

字典树是一种数据结构 而不是算法

词典中的每个“单词”就是从根节点出发一直到某一个目标节点的路径

路径中每条边的字母连起来就是一个单词

图和解释的来源: 字典树(Trie)详解 – Seaway-Fu – 博客园 (cnblogs.com)

那就围绕着要实现的几个功能看看

插入字符串

迭代器遍历字符串

从根节点开始和字符串中的每个字母比较

如果存在下一次就从这个节点开始

不存在就创建一个新的节点记录在 数组的对应位置上

下一次从这个新节点开始

查找前缀

同样从根节点开始和遍历的字符串比较

如果存在下一次就从这开始

不存在说明字典树中不包含该前缀,返回空指针。

重复直到返回空指针或搜索完前缀的最后一个字符

如果搜索到了前缀的末尾,就说明字典树中存在该前缀

如果前缀末尾对应节点的 isEnd 为真,则说明字典树中存在该字符串

《208. 实现 Trie (前缀树)》有1个想法

  1. Pingback: 每日一题——472. 连接词 – 海星peter的海滩

发表评论

您的电子邮箱地址不会被公开。