Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
Trie
添加
IsWord表示一个单词的结束
单词字母内容由 平衡二叉树 存储
查询
非递归实现
递归实现
前缀
Ternary Search Trie
待更新
public class Trie
{
private class Node
{
public bool IsWord;
public SortedDictionary<char, Node> Next;
public Node(bool isWord)
{
IsWord = isWord;
Next = new SortedDictionary<char, Node>();
}
public Node():this(false)
{
}
}
private Node root;
private int size;
public Trie()
{
root = new Node(false);
size = 0;
}
public int Size()
{
return size;
}
// 向 Trie 中添加一个 单词
public void Add(string word)
{
Node cur = root;
foreach (var ch in word)
{
if (!cur.Next.ContainsKey(ch))
cur.Next[ch] = new Node(false);
cur = cur.Next[ch];
}
if (cur.IsWord) return;
cur.IsWord = true;
++size;
}
// 查询单词是否在 Trie 中 非递归实现
public bool Contains(string word)
{
Node cur = root;
foreach (var ch in word)
{
if (!cur.Next.ContainsKey(ch))
return false;
cur = cur.Next[ch];
}
return cur.IsWord;
}
// 递归实现
public bool ContainsRecursive(string word)
{
return Contains(root, word, 0);
}
private bool Contains(Node node, string str, int index)
{
if (index > str.Length - 1)
return node.IsWord;
if (!node.Next.ContainsKey(str[index]))
return false;
return Contains(node.Next[str[index]], str, ++index);
}
public bool IsPrefix(string prefix)
{
Node cur = root;
foreach (var ch in prefix)
{
if (!cur.Next.ContainsKey(ch))
return false;
cur = cur.Next[ch];
}
return true;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/197734.html原文链接：https://javaforall.net
