PrefixTree.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace PrefixTree
{
	public class Node
	{
		private const short rootLetterValue = 97;

		public char Letter;
		public Node[] Nodes;
		public bool IsWord;

		public Node(char letter)
		{
			Letter = letter;
			Nodes = new Node[26];
			IsWord = false;
		}

		public Node AddNode(Node node)
		{
			int letterIndex = node.Letter - rootLetterValue;

			// If node doesn't already exist, add it
			if (Nodes[letterIndex] == null)
			{
				Nodes[letterIndex] = node;
			}

			return Nodes[letterIndex];
		}

		public bool FindPrefix(string word)
		{
			Node nodeIterator = this;
			int currentIndex = 0;

			while (nodeIterator != null && currentIndex < word.Length)
			{
				char letter = word[currentIndex];
				nodeIterator = nodeIterator.Nodes[letter - rootLetterValue];

				currentIndex++;
			}

			return (nodeIterator != null);
		}

		public bool FindWord(string word)
		{
			Node nodeIterator = this;
			int currentIndex = 0;

			while (nodeIterator != null && currentIndex < word.Length)
			{
				char letter = word[currentIndex];
				nodeIterator = nodeIterator.Nodes[letter - rootLetterValue];

				currentIndex++;
			}

			return (nodeIterator != null && nodeIterator.IsWord);
		}

		public Node GetPrefixNode(string word)
		{
			Node nodeIterator = this;
			int currentIndex = 0;

			while (nodeIterator != null && currentIndex < word.Length)
			{
				char letter = word[currentIndex];
				nodeIterator = nodeIterator.Nodes[letter - rootLetterValue];

				currentIndex++;
			}

			return nodeIterator;
		}
	}

	public class PrefixTree
	{
		public Node rootNode;

		public PrefixTree()
		{
			rootNode = new Node(' ');
		}

		public void AddWord(string word)
		{
			var nodeIterator = rootNode;

			for (int i = 0; i < word.Length; i++)
			{
				char letter = word[i];

				nodeIterator = nodeIterator.AddNode(new Node(letter));
			}

			nodeIterator.IsWord = true;
		}

		public bool FindPrefix(string word)
		{
			return rootNode.FindPrefix(word);
		}


		public List<string> GetWordsFromPrefix(string prefix)
		{
			Node prefixRoot = rootNode.GetPrefixNode(prefix);

			List<string> words = new List<string>();
			GetWords(prefixRoot, words);

			prefix = prefix.Remove(prefix.Length - 1);
			words = words.Select(suffix => prefix + suffix).ToList();
			return words;
		}


		public void GetWords(Node root, List<string> words, string word = "")
		{
			if (root.IsWord)
				words.Add(word + root.Letter);

			for (int i = 0; i < 26; i++)
			{
				if (root.Nodes[i] != null)
					GetWords(root.Nodes[i], words, word + root.Letter);
			}
		}

		public void MatchWordsFromMatrix(char[,] matrix, bool[,] visitedLocations, int currentRow, int currentColumn, string word, ref List<string> words)
		{
			visitedLocations[currentRow, currentColumn] = true;
			word = word + matrix[currentRow, currentColumn];

			if (rootNode.FindWord(word))
			{
				words.Add(word);
			}

			for (int i = currentRow - 1; i <= currentRow + 1 && i < matrix.GetLength(0); i++)
			{
				for (int n = currentColumn - 1; n <= currentColumn + 1 && n < matrix.GetLength(1); n++)
				{
					if (i >= 0 && n >= 0 && !visitedLocations[i,n])
						MatchWordsFromMatrix(matrix, visitedLocations, i, n, word, ref words);
				}
			}

			word.Remove(word.Length - 1, 1);
			visitedLocations[currentRow, currentColumn] = false;
		}

		public List<string> FindWordsInMatrix(char[,] matrix)
		{
			List<string> words = new List<string>();

			var visitedLocations = new bool[3, 3];
			string blankString = "";

			for (int i = 0; i < 3; i++)
			{
				for (int n = 0; n < 3; n++)
				{
					this.MatchWordsFromMatrix(matrix, visitedLocations, i, n, blankString, ref words);
				}
			}

			return words;

		}

	}
}