/// <summary>
/// trie中的键通常是字符串，但也可以是其它的结构。trie的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或者形状的排列。比如，bitwise trie中的键是一串比特，可以用于表示整数或者内存地址。
///使用Trie往往是为了实现单词查找或者统计频率.
/// </summary>
public class TNode
{
    public Dictionary<char, TNode> Childs { get; set; }
    public bool EndOfWrod { get; set; }
}

public class Trie
{
    private TNode _root = new TNode();

    public void Add(string word)
    {
        var currentNode = _root;
        for (int i = 0; i < word.Length; i++)
        {
            if (!currentNode.Childs.ContainsKey(word[i]))
            {
                currentNode.Childs.Add(word[i], new TNode());
            }
            currentNode = currentNode.Childs[word[i]];
        }
        currentNode.EndOfWrod = true;
    }

    public bool Contains(string word)
    {
        return GetLastNode(word).EndOfWrod;
    }

    public bool StartWith(string preFix)
    {
        return GetLastNode(preFix) != null;
    }

    private TNode GetLastNode(string word)
    {
        var currentNode = _root;
        for (int i = 0; i < word.Length; i++)
        {
            if (!currentNode.Childs.ContainsKey(word[i]))
            {
                return null;
            }
            currentNode = currentNode.Childs[word[i]];
        }
        return currentNode;
    }
}