is FIND WORDS in P?

Question

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?

Answer 1

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)$.

Answer 2

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)$.