208. 实现 Trie (前缀树)
2021/12/16 23:13:58
本文主要是介绍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 。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/implement-trie-prefix-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Trie { private Node root; class Node { Node[] children = new Node[26]; boolean end = false; } public Trie() { this.root = new Node(); } public void insert(String word) { Node cur = root; for (int i = 0; i < word.length(); ++i) { int path = word.charAt(i) - 'a'; if (cur.children[path] == null) { cur.children[path] = new Node(); } cur = cur.children[path]; } cur.end = true; } public boolean search(String word) { Node cur = root; for (int i = 0; i < word.length(); ++i) { int path = word.charAt(i) - 'a'; if (cur.children[path] == null) { return false; } cur = cur.children[path]; } return cur.end; } public boolean startsWith(String word) { Node cur = root; for (int i = 0; i < word.length(); ++i) { int path = word.charAt(i) - 'a'; if (cur.children[path] == null) { return false; } cur = cur.children[path]; } 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); */
这篇关于208. 实现 Trie (前缀树)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署