Phone number combinations using Trie

Main.cs

using System;

namespace PhoneCombinations
{
    public class Program
    {
        public static void Main(string[] args)
        {
            Trie trie = new Trie();
            trie.Insert("eat");
            trie.Insert("ear");
            trie.Insert("east");
            trie.Insert("dart");
            
            var number = "3278";
            var combinations = trie.GetWordsFromNumber(number);
            
            Console.WriteLine("Possible words for {0} are", number);
            foreach (var word in combinations) {
                Console.WriteLine(word);
            }
        }
    }
}

Trie.cs

using System;
using System.Collections.Generic;
using System.Text;

namespace PhoneCombinations {

	public class TrieNode {
		
		public TrieNode() {
			this.Children = new List<TrieNode>();
		}
		
		public TrieNode(char key, char value) {
			this.Key = key;
			this.Value = value;
			this.Children = new List<TrieNode>();
		}
		
		public char Key { get; set; }
		public char Value { get; set; }
		public bool IsWord { get; set; }
		public List<TrieNode> Children { get; set; }
	}
	
	public class Trie {
		private TrieNode root;
		
		private Dictionary<char, string> digitToLettersMap;
		
		private Dictionary<char, char> letterToDigitMap;
		
		private void init() {
			digitToLettersMap = new Dictionary<char, string>();
			digitToLettersMap.Add('2', "abc");
			digitToLettersMap.Add('3', "def");
			digitToLettersMap.Add('4', "ghi");
			digitToLettersMap.Add('5', "jkl");
			digitToLettersMap.Add('6', "mno");
			digitToLettersMap.Add('7', "pqrs");
			digitToLettersMap.Add('8', "tuv");
			digitToLettersMap.Add('9', "wxyz");
	
			letterToDigitMap = new Dictionary<char, char>();
			letterToDigitMap.Add('a', '2');
			letterToDigitMap.Add('b', '2');
			letterToDigitMap.Add('c', '2');
			letterToDigitMap.Add('d', '3');
			letterToDigitMap.Add('e', '3');
			letterToDigitMap.Add('f', '3');
			letterToDigitMap.Add('g', '4');
			letterToDigitMap.Add('h', '4');
			letterToDigitMap.Add('i', '4');
			letterToDigitMap.Add('j', '5');
			letterToDigitMap.Add('k', '5');
			letterToDigitMap.Add('l', '5');
			letterToDigitMap.Add('m', '6');
			letterToDigitMap.Add('n', '6');
			letterToDigitMap.Add('o', '6');
			letterToDigitMap.Add('p', '7');
			letterToDigitMap.Add('q', '7');
			letterToDigitMap.Add('r', '7');
			letterToDigitMap.Add('s', '7');
			letterToDigitMap.Add('t', '8');
			letterToDigitMap.Add('u', '8');
			letterToDigitMap.Add('v', '8');
			letterToDigitMap.Add('w', '9');
			letterToDigitMap.Add('x', '9');
			letterToDigitMap.Add('y', '9');
			letterToDigitMap.Add('z', '9');
		}
		
		public Trie() {
			root = new TrieNode();
			init();
		}
		
		// Time: O(n)
		public void Insert(string word) {
			var currentNode = root;
			foreach(var ch in word) {
				currentNode = insert(currentNode, ch);
			}
			
			currentNode.IsWord = true;	
		}
		
		private TrieNode insert(TrieNode node, char ch) {
			foreach(var child in node.Children) {
				if (child.Value == ch) {
					return child;
				}
			}
			
			TrieNode newNode = new TrieNode(letterToDigitMap[ch], ch);
			node.Children.Add(newNode);
			
			return newNode;
		}
		
		// Time: m * O(n)
		// m: Number of possible words
		// n: Length of each word
		// Worst case: O(n ^ 2) when m ~ n
		public List<string> GetWordsFromNumber(string number) {			
			var result = new List<string>();
			
			if (String.IsNullOrEmpty(number)) {
				return result;
			}
			
			char firstDigit = number[0];
			foreach (var child in root.Children) {
				if (child.Key == firstDigit) {
					var subResult = getWordsFromNumber(child, number, new StringBuilder(""));
					if (subResult.Count > 0) {
						result.AddRange(subResult);
					}
				}
			}
			
			return result;
		}
		
		private List<string> getWordsFromNumber(TrieNode node, string number, StringBuilder prefix) {
			char firstDigit = number[0];
			
			var result = new List<string>();
			if (node.Key == firstDigit) {
				prefix.Append(node.Value);
				
				if (number.Length == 1) {
					if (node.Children.Count == 0) {
						result.Add(prefix.ToString());	
					}
				} else {
					foreach (var child in node.Children) {
						var subResult = getWordsFromNumber(child, number.Substring(1), prefix);
						if (subResult.Count > 0) {
							result.AddRange(subResult);
						}
					}
				}
				
				prefix.Remove(prefix.Length - 1 , 1);
			}
			
			return result;
		}
	}	
}