5
$\begingroup$

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?

$\endgroup$
16
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.