WordFind.txt

Word Find:
Given any 2x2 array of letters and a Dictionary.isWord( x:string ):boolean method, write code (real or pseudo) that will output an array of all the English words found.

Rules:
1.  Words are found by stringing any number of neighboring letters together.  For example: Using the example input below, the word TAB may be formed by concatenating [0][1], [1][1], [2][1].
2.  Neighbors are considered touching on any side, including diagonally.  This means that any non-edge letter will have 8 neighbors.  For example: The word LABS may be formed by concatenating [2][0], [1][1], [2][1], [1][0].
3.  You may not use the same coordinate more than once in the same word.  For example: The word PEOPLE ([3][0], [3][1], [4][0], [4][1], [4][2], [3][1]) would not qualify because [3][1] was used twice.

Example input:
  [[ I, T, N, D, O ],
   [ S, A, K, X, N ],
   [ L, B, Z, M, E ],
   [ P, E, L, M, E ],
   [ O, P, L, S, T ]]

Extra Credit:
Assuming Dictionary.isWord is O(1), please analyze the runtime of your solution.  Can you improve on it?



Notes
-------
This one took me a bit longer to settle on a strategy.  I decided to first traverse the set building out a list of chars of possible options for each character.  This gives me a list of strings that I can then use similar logic from the palindrome excersize but looking for dictionary words instead.

My first challenge was to figure out an algorithm to identify neighbors for each letter across the 2d array.  Then I need to represent that traversal as a graph structure that can be evaluated to concatonate the letters into string sets which can then be searched for words.  This turned out to be a simple n-tree.

My first implementation is a pretty bruteforce approach especially in how the neighbors are identified.  There is most definitely a more elegant solution for traversing unique paths through a matrix.  

The goal of this implementation is to get the largest possible word from starting from each letter in the set.  For each letter, every possible path is found, some examples from the Example input would be:

MXDNKZLLPEBATISLPO
MXDNKZLLSMEENO
MXDNKZLLSMET

There is obvious opportunity here to only search the common paths once

improve...
use the locations as a key to elimitate the need to search from other areas of the set.