using System;

public class Program

{

    public static void Main()

    {

        Trie t = new Trie();

        t.Insert("word");

        t.Insert("work");

        t.Insert("wood");

        Console.WriteLine("Search 'word' => " + t.Search("word"));

        Console.WriteLine("StartsWith 'wor' => " + t.StartsWith("wor"));

    }

    public class Trie

    {

        public class TrieNode

        {

            public bool IsEnd;

            public TrieNode[] Children = new TrieNode[26];

        }

        private TrieNode root;

        public Trie()

        {

            root = new TrieNode();

        }

        public void Insert(string word)

        {

            TrieNode node = root;

            for(int i = 0; i < word.Length; i++)

            {

                char c = word[i];

                if(node.Children[c - 'a'] == null)

                    node.Children[c - 'a'] = new TrieNode();

                node = node.Children[c - 'a'];

            }

            node.IsEnd = true;

        }

        public bool Search(string word)

        {

            TrieNode node = root;

            for(int i = 0; i < word.Length; i++)

            {

                char c = word[i];

                if(node.Children[c - 'a'] == null)

                    return false;

                node = node.Children[c - 'a'];

            }

            return node.IsEnd;

        }

        public bool StartsWith(string prefix)

        {

            TrieNode node = root;

            for(int i = 0; i < prefix.Length; i++)

            {

                char c = prefix[i];

                if(node.Children[c - 'a'] == null)

                    return false;

                node = node.Children[c - 'a'];

            }

            return true;

        }

    }

}