Printing all possible words from a 2D array of characters

Question

Stumbled upon this interview question recently,

Given a 2-dimensional array of characters and a dictionary in which a word can be searched in O(1) time. Need to print all the words from array which are present in dictionary. Word can be formed in any direction but has to end at any edge of array.(Need not worry much about the dictionary)

Input:

a f h u n
e t a i r
a e g g o
t r m l p

Output:

after
hate
hair
air
eat
tea

Note: Here "egg" is not a dictionary word because its not ending at the edge of array.

I've seen similar questions before, but was never able to think of a good algorithm to solve these kind of problems. Any help on how to approach these kind of problems (forming words from arrays of characters) will be highly helpful.

(The only way I could think of is to find all possible permutations of characters in the 2D array, and check if it ends on the edge of the array, and check if the permutation is a valid word from the dictionary in O(1) time)

Answer 1

Turn the array into a graph so that each cell [i,j] has an edge shared with each one of its 4 neighbors [i+1,j], [i-1,j], [i,j+1], [i,j-1]. Then run DFS at each array-edge-cell and and keep checking the dictionary whether the word in reverse is in it.

Answer 2

You did not mention anything about a character can be used only once - so without this restriction is problem of "Can we generate k (or more) different words?" is undecideable.¹.

(With a constraint on the number of "visites" per element there are finite number of possibilities and the claim and proof does not hold of course).

Proof:
It is known that there is no algorithm A that can decide if a terminating algorithm B returns true for k or more different inputs. (will look for citation for this claim later if needed, trust me for now).

We will show that given an algorithm A that says if there are k or more generated words - we can decide if there are k or more different inputs that yield "true":

1. Let the (terminating) algorithm that decides if there are k or more generated words be M.

2. Without loss of generality - assume binary alphabet (we can represent everything with it).

3. Let:

    array = 0 1 
            0 1
   

   Note we can generate any binary word while walking on this array.

Algorithm A:
input: algorithm B, natural number n
output: true if and only if algorithm B answers "true" for n or more different inputs.
The algorithm:
(1) use B(word) as the black box dictionary - if the answer is true, then word is in dictionary.
(2) use array as the array.
(3) Run M on (array,dictionary,n), and answer like it.

Note that if M answered true -> there are n or more accepted words -> there are n or more different inputs to B that yields true (definition of dictionary and since we can generate every input with array) -> the answer to the problem is true.
(if the algorithm answered false the proof is similar).

QED

Conclusion:
If we can repeat a character in the array more then a once (or to be exact - unbounded number of times) - then the problem is unsolveable without any information on the dictionary.

---

(1) An undecideble problem is a problem where there is no algorithm that can answer TRUE/FALSE correctly in 100% of the cases - For every algorithm, there is some case where the algorithm will get "stuck" in an infinite loop (or give a wrong answer). The most common of "undecideable" problems is the Halting Problem - which says - there is no algorithm A that can take any algorithm B and answer if B stops for some input w.