CareerCup

From my understanding, a dictionary is a set of words, lexically sorted, providing a meaning to the given key/entry in it.

In your case, do you have a list of the "words" and their meanings/values/whatever and need the dictionary for random access of any of the available words?

If that could be the case, I would suggest a hashMap as underlying data structure where key is the word itself.

To save space we could use Trie data structure (prefix tree) to save dictionary words. using Trie will allow us to reuse the shared prefixes of English words, e.g. car and cat will have the "ca" as prefix for both and then the last characters will make the full words. Complexity for this implementation is nLogn since Trie is basically a tree, if time is the concern then hash map can be used for a better time vs space advantage given by Trie.

you would need to have a good hashing algorithm to hash out keys for all the values

public class AutoComplete
	{

	    class Node
		{
			public string prefix;
			public Dictionary<char, Node> dict;
			public bool isWord;
			public Node(string prefix)
			{
				this.prefix = prefix;
				this.dict = new Dictionary<char, Node>();
			}

		}

	   Node trie;

		public AutoComplete(string[] words)
		{
			trie = new Node("");
			foreach (var word in words)
			{
				InsertWord(word);
			}
		}

		private void InsertWord(string word)
		{
			Node curr = trie;
			for (int i = 0; i < word.Length; i++)
			{
				if (!curr.dict.ContainsKey(word[i]))
				{
					curr.dict.Add(word[i], new Node(word.Substring(0, i + 1)));
				}
				curr = curr.dict[word[i]];
				if (i == word.Length - 1)
				{
					curr.isWord = true;
				}
			}
		}

		public List<string> GetPrefix(string pre)
		{
			var prefixList = new List<string>();

			Node curr = trie;
			foreach (var c in pre)
			{
				if (curr.dict.ContainsKey(c))
					curr = curr.dict[c];
				else
					return prefixList;
			}
			FindPrefix(curr, prefixList);
			return prefixList;
		}

		private void FindPrefix(Node n,  List<string> prefixList)
		{
			if (n.isWord)
				prefixList.Add(n.prefix);


			foreach (var item in n.dict.Keys)
			{
				FindPrefix(n.dict[item], prefixList);
			}
		}
	  }

public class AutoComplete
	{

	    class Node
		{
			public string prefix;
			public Dictionary<char, Node> dict;
			public bool isWord;
			public Node(string prefix)
			{
				this.prefix = prefix;
				this.dict = new Dictionary<char, Node>();
			}

		}

	   Node trie;

		public AutoComplete(string[] words)
		{
			trie = new Node("");
			foreach (var word in words)
			{
				InsertWord(word);
			}
		}

		private void InsertWord(string word)
		{
			Node curr = trie;
			for (int i = 0; i < word.Length; i++)
			{
				if (!curr.dict.ContainsKey(word[i]))
				{
					curr.dict.Add(word[i], new Node(word.Substring(0, i + 1)));
				}
				curr = curr.dict[word[i]];
				if (i == word.Length - 1)
				{
					curr.isWord = true;
				}
			}
		}

		public List<string> GetPrefix(string pre)
		{
			var prefixList = new List<string>();

			Node curr = trie;
			foreach (var c in pre)
			{
				if (curr.dict.ContainsKey(c))
					curr = curr.dict[c];
				else
					return prefixList;
			}
			FindPrefix(curr, prefixList);
			return prefixList;
		}

		private void FindPrefix(Node n,  List<string> prefixList)
		{
			if (n.isWord)
				prefixList.Add(n.prefix);


			foreach (var item in n.dict.Keys)
			{
				FindPrefix(n.dict[item], prefixList);
			}
		}
	  }

public class AutoComplete
{

class Node
{
public string prefix;
public Dictionary<char, Node> dict;
public bool isWord;
public Node(string prefix)
{
this.prefix = prefix;
this.dict = new Dictionary<char, Node>();
}

}

Node trie;

public AutoComplete(string[] words)
{
trie = new Node("");
foreach (var word in words)
{
InsertWord(word);
}
}

private void InsertWord(string word)
{
Node curr = trie;
for (int i = 0; i < word.Length; i++)
{
if (!curr.dict.ContainsKey(word[i]))
{
curr.dict.Add(word[i], new Node(word.Substring(0, i + 1)));
}
curr = curr.dict[word[i]];
if (i == word.Length - 1)
{
curr.isWord = true;
}
}
}

public List<string> GetPrefix(string pre)
{
var prefixList = new List<string>();

Node curr = trie;
foreach (var c in pre)
{
if (curr.dict.ContainsKey(c))
curr = curr.dict[c];
else
return prefixList;
}
FindPrefix(curr, prefixList);
return prefixList;
}

private void FindPrefix(Node n, List<string> prefixList)
{
if (n.isWord)
prefixList.Add(n.prefix);


foreach (var item in n.dict.Keys)
{
FindPrefix(n.dict[item], prefixList);
}
}
}