前缀树和字典树_arch前缀是什么意思

前缀树和字典树_arch前缀是什么意思字典树/前缀树_字典树

字典树/前缀树

Trie(发音类似 “try”)或者说 前缀树(字典树) 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。主要思想是利用字符串的公共前缀来节约存储空间。很好地利用了串的公共前缀,节约了存储空间。字典树主要包含两种操作,插入和查找。

比如,我们要怎么用树存下单词”abc”,“abb”,“bca”,”bc”呢?见图
在这里插入图片描述在图中,红点代表有一个以此节点为终点的单词。然后,我们如果要查找某个单词如s=“abc”,就可以这样
在这里插入图片描述
在这里,s=“abc” 的每一个字母都在树中被查到了,并且最后一个点是红色代表有一个在此结束的单词,查询成功。而 s=“bb” 的第二个字母没有在相应位置被查到,因此”bb”不在字典中。至于s=“ab” 虽然单词中每个点都被查到了,但是由于结尾的字母在树中没有标红,因此也是不在字典中。

对于字典树的每次查找,时间复杂度为log级别,比暴力快多了。

例题

字典树有多中实现方法,可以通过数组存储,也可以通过哈希表来存储,本文我们主要讲解这两中方法:

力扣208题:实现 Trie (前缀树)

请你实现 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 * 104 次

实现(Java)

class Trie { 
   
    private Trie[] children;		// 存放子结点,当不为null时,即当前位置被激活
    private boolean isEnd;			// 判断此位置是否是单词的结尾

    public Trie() { 
   
        children = new Trie[26];
    }
    
    public void insert(String word) { 
   
        Trie node = this;     
        for(int i = 0; i < word.length(); i++) { 
   
            char ch = word.charAt(i);
            int index = ch - 'a';
            if(node.children[index] == null) { 
   
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) { 
   
        Trie node = this;
        for(int i = 0; i < word.length(); i++) { 
   
            char ch = word.charAt(i);
            int index = ch - 'a';
            if(node.children[index] == null) { 
   
                return false;
            }
            node = node.children[index];
        }
        return node != null && node.isEnd == true;
    }
    
    public boolean startsWith(String prefix) { 
   
        Trie node = this;
        for(int i = 0; i < prefix.length(); i++) { 
   
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if(node.children[index] == null) { 
   
                return false;
            }
            node = node.children[index];
        }
        return true;
    }
}

/** * 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); */

力扣648题:单词替换

在英语中,我们有一个叫做 词根(root) 的概念,可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如,词根an,跟随着单词 other(其他),可以形成新的单词 another(另一个)。

现在,给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根,则用最短的词根替换它。

你需要输出替换之后的句子。

示例 1:

输入:dictionary = [“cat”,“bat”,“rat”], sentence = “the cattle was rattled by the battery”
输出:“the cat was rat by the bat”

示例 2:

输入:dictionary = [“a”,“b”,“c”], sentence = “aadsfasf absbs bbab cadsfafs”
输出:“a a b c”

提示:

  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] 仅由小写字母组成。
  • 1 <= sentence.length <= 10^6
  • sentence 仅由小写字母和空格组成。
  • sentence 中单词的总量在范围 [1, 1000] 内。
  • sentence 中每个单词的长度在范围 [1, 1000] 内。
  • sentence 中单词之间由一个空格隔开。
  • sentence 没有前导或尾随空格。

实现(Java)

class Solution { 
   
    public String replaceWords(List<String> dictionary, String sentence) { 
   
        Trie trie = new Trie();
        for(String word : dictionary) { 
   
            Trie cur = trie;
            for(int i = 0; i < word.length(); i++) { 
   
                char ch = word.charAt(i);
                cur.children.putIfAbsent(ch, new Trie());
                cur = cur.children.get(ch);
            }
            cur.children.put('#', new Trie());
        }

        String[] words = sentence.split(" ");
        for(int i = 0; i < words.length; i++) { 
   
            words[i] = find(words[i], trie);
        }
        return String.join(" ", words);
    }

    public String find(String word, Trie trie) { 
   
        for(int i = 0; i < word.length(); i++) { 
   
            if(trie.children.containsKey('#'))
                return word.substring(0, i);
            Character ch = word.charAt(i);
            if(!trie.children.containsKey(ch)) { 
   
                return word;
            }
            trie = trie.children.get(ch);
        }
        return word;
    }

}

class Trie { 
   	
	// 哈希表存放<字符, 下一个字符>,注意当下一个字符有'#'时表示该字符为单词结尾
    Map<Character, Trie> children;	
    	
    public Trie() { 
   
        children = new HashMap<Character, Trie>();
    }
}

前缀树就先总结到这里,之后遇到其他方法还会继续更新哦,谢谢大家的点赞支持!

今天的文章前缀树和字典树_arch前缀是什么意思分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/74962.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注