实现前缀树(Trie树)-LeetCode208
一、题目描述
Trie(发音类似 "try")或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。
请你实现 Trie 类
1)Trie() 初始化前缀树对象。 2)void insert(String word) 向前缀树中插入字符串 word 。 3)boolean search(String word) 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false 。 4)boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false
二、解题思路
(1)什么是trie树?
trie树又名前缀树、字典树,其作用之一即为字符串的前缀匹配 ,如图
当匹配前缀时,从数的根节点开始一层一层向下查找(以空间换时间)
2)trie类的属性
boolean isEnd:当前节点是否为存储字符串的末尾(在search()中对所需查找的字符串进行判断) Trie[] children:保存当前节点的所有子节点,长度为26,代表26个字符的存储位置
三、代码实现
class Trie { //存放当前节点的子节点(不是指针,但又相当于指针) private Trie[] children; //当前节点是否为末尾 private boolean isEnd; public Trie() { //根节点的创建 children = new Trie[26]; isEnd = false; } //将字符串插入树中 public void insert(String word) { Trie node=this; for (int i = 0; i < word.length(); i++) { char ch=word.charAt(i); int chToInt=ch-a; if(node.children[chToInt]==null){ node.children[chToInt]=new Trie(); } node=node.children[chToInt]; } node.isEnd=true; } //search:查询前缀树中是否有这样的字符串,其isEnd标志为true public boolean search(String word) { if(startsWith(word)&&startsWithPrefix(word).isEnd){ return true; } return false; } //查询前缀树中是否有当前前缀prefix public boolean startsWith(String prefix) { if(startsWithPrefix(prefix)!=null){ return true; } return false; } public Trie startsWithPrefix(String prefix){ Trie node = this; char ch; int chToInt; int flag=1; for (int i = 0; i < prefix.length(); i++) { ch = prefix.charAt(i); chToInt=ch-a; if(node.children[chToInt]!=null){ node=node.children[chToInt]; }else { flag=0; break; } } if(flag==1){ return node; } return null; } }