208. 实现 Trie (前缀树)
public class Trie
{
class Node
{
public readonly Node[] child = new Node[26];
public bool isEnd;
public void Insert(CharEnumerator chars)
{
ref var node = ref child[chars.Current - 'a'];
if (node == null)
node = new Node();
if (chars.MoveNext())
node.Insert(chars);
else
node.isEnd = true;
}
}
Node root = new Node();
public Trie() { root.isEnd = true; }
public void Insert(string word)
{
if (word == string.Empty)
return;
var itor = word.GetEnumerator();
itor.MoveNext();
root.Insert(itor);
}
public bool Search(string word)
{
var node = root;
foreach (var ch in word)
{
ref var next = ref node.child[ch - 'a'];
if (next == null)
return false;
node = next;
}
return node.isEnd;
}
public bool StartsWith(string prefix)
{
var node = root;
foreach (var ch in prefix)
{
ref var next = ref node.child[ch - 'a'];
if (next == null)
return false;
node = next;
}
return true;
}
}