[力扣] 算法 208 (C#)

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;
    }
}

发表评论