# is FIND WORDS in P?

FIND WORDS is the following decision problem:

Given a list of words L and a Matrix M, are all words in L also in M? The words in M can be written up to down, down to up, left to right, right to left, diagonal-left-up, diagonal-left-down, diagonal-right-up and diagonal-righ-down. To be specific this is the classic game that can be found in the puzzling week: FIND WORDS

Now this decision problem clearly is in NP because, given a certificate with the positions of the words in the matrix (indexes), a verifier can check it in polynomial time.

My question is this: are we aware of Turing Machines that decide this language in polynomial time?

Your language is in P. Suppose that the matrix is $$n\times n$$ and that the words have total length $$\ell$$. Each word can start at at most $$n^2$$ positions and be written in $$O(1)$$ many orientations, for a total of $$O(n^2)$$ possible placements. Checking each one costs at most $$O(m)$$, where $$m$$ is the length of the word. In total, we obtain an algorithm whose running time is $$O(\ell n^2)$$, which is quadratic in the input length.
Using a trie or similar data structure, you can probably improve this to linear time $$O(n^2 + \ell)$$.
Let $$M$$ be a $$n \times n$$ matrix. And I am searching a word $$l_ll_2 \dots l_k$$ of length $$k$$. Now first we search $$l_1$$ in $$M$$. It takes $$O(n^2)$$ time. For each successful search, we look at all eight direction (up to down, down to up, left to right, right to left, diagonal-left-up, diagonal-left-down, diagonal-right-up and diagonal-right-down) and check if $$l_2 \dots l_k$$ exists or not. At one direction it takes $$O(k)$$ time. So overall running time is $$O(kn^2)$$.