102 实现Trie(前缀数)

2024-01-08 15:53:13

问题描述:Trie(发音类似try)或者说前缀树是一种树形数据结构,用于高效地存储和检索字符串数据集中地键。这一数据结构有相当多的应用情景,例如自动不写和拼写检查。请你实现Trie类:Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word,Boolean?search(String word)如果字符串word在前缀树中,返回true(即检索之前已经插入)否则返回false,Boolean startsWith(String prefix)如果之前已经插入的word的前缀之一为prefix,返回true,否则返回false。

问题分析:前缀树又叫字典树,首先定义一个节点dictNode,且每个节点有26个分支,定义一个dictRoot,其中有一个dictNode作为根节点,并实现insert,serach,startwith等方法。

class dictNode
{
public String word;
public dictNode[26] childNode;
dictNode()
{
word=null;
childNode=new dictNode[26];
}
}
class dictRoot()
{
public dictNode root;
dictRoot()
{
root=new dictNode();
}
public void insert(String word)
{
dictNode parent=root;
for(int i=0;i<word.length();i++)
{
if(parent.childNode(s.charAt(i)-'a')==null){parent.chileNode(s.charAt(i)-'a')=new dictnode();}
parent=parent.childNode(s.charAt(i)-'a');
}
parent.word=word;
}
public Boolean search(String word)
{
dictnode parent=root;
for(int i=0;i<word.length();i++)
{
if(parent.childNode(s.charAt(i)-'a')==null){return false;}
parent=arent.childNode(s.charAt(i)-'a');
}
if(parent.word.equals(word)){return true;}
return false;
}
public Boolean preFix(String word)
{
dictnode parent=root;
for(int i=0;i<word.length();i++)
{
if(parent.childNode(s.charAt(i)-'a')==null){return false;}
parent=arent.childNode(s.charAt(i)-'a');
}
return true;
}
}

文章来源:https://blog.csdn.net/qq_52299902/article/details/135405931
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。