## Epic Systems Interview Question

**Country:**United States

Not really... How would that solve this problem? The order of traversal matters, because otherwise you might not find the given word, besides, would you start a DFS from all positions in the grid? Not very efficient...

Why not simply to search for the first letter of word and start propagation in all possible directions if we found it? Don't understand how DFS will help in this situation.

GK, that's an obvious choice (brute force), but I think we're supposed to find a solution that is more efficient.

Brute force in this case is O(n^3), we should be aiming for O(n^2)

(To make it simple, I considered the grid to be n x n and the searched word to be O(n)).

Zoli, it is essentially DFS(grid position).

Just try starting it at every grid position.

There are implicit arcs from every grid position to every adjacent grid position.

"return" if you meet a character on the grid that doesn't match the corresponding level of character in the given word to allow for a different path to be search

A match is hit when all characters in the given word are exhausted.

BigKdotAtTdot, I see, so that means n^2 DFS runs.

I see 2 problems with this approach:

1. It is not efficient: the overall algorithm would be O(n^3)

2. It still does not solve the problem. I think the original problem meant that the word has to be straight, that is, the whole word has to be readable in one of the 8 directions. Your DFS "breaks" the word, so it might go right 2 positions, then down 2 positions. This way it might find occurences which shouldn't be considered.

Good idea.

To refine the solution a bit, I suppose you were thinking the following:

Take the first line, do a KMP pattern matching on it using the given word. Do this for every line in the matrix. Then do this same thing in all 4 directions (left-right, up-down, top left - bottom right, bottom left - top right). After this, take the reverse of the word and do the whole algorithm again (to check the inverse directions). Of course this last step is not necessary, you can just implement the 8 directions as well.

This will go over the matrix 8 times with the KMP algorithm, which will still keep it at O(n^2) which is the best possible achievable time complexity given that we need to read the grid at least once.

Something similar to this appeared in Code Chef:

Here is the problem statement:

Given a M by N grid of letters, (1<=M,N<=50), and a

list of words, find the location in the grid at which the word can be found. A

word matches a straight, uninterrupted line of letters in the grid. A word can

match the letters in the grid in the grid regardless of case (i.e. upper and

lower case letters are to be treated as the same). The matching can be done in

any of the eight directions either horizontally, vertically or diagonally

through the grid.

Input

The input will contain one or more test cases. The

first line of each test case begins with a pair of integers, M followed by N,

1<=M,N<=50 on a single line. The next M lines contain N letters each; this is

the grid of letters in which the words of the list must be found. The letters in

the grid may be in upper or lower case. Following the grid of letters, another

integer K appears on a line by itself (1<=K<=20). The next K lines of input

contain the list of words to search for, one word per line. These words may

contain upper and lower case letters only (no spaces, hyphens or other

non-alphabetic characters).The input will end with two zeroes for M and N.

Output

For each word in the word list, output a pair of integers representing the

location of the corresponding word in the grid must be output. The integers must

be separated by a single space. The first integer is the line in the grid where

the first letter of the given word can be found (1 represents the topmost line

in the grid, and m represents the bottommost line). The second integer is the

column in the grid where the first letter of the given word can be found (1

represents the leftmost column in the grid, and n represents the rightmost

column in the grid). If a word can be found more than once in the grid, then the

location which is the output should correspond to the uppermost occurrence of

the word (i.e. the occurrence which places the first letter of the word closest

to the top of the grid). If two or more words are uppermost, the output should

correspond to the leftmost of these occurrences. All words can be found at least

once in the grid. Separate the output of each test case with a blank line.

And here is the best solution submitted by bsakthikumar

```
#include <stdio.h>
#include <ctype.h>
#include <string.h>
char a[50][50];
int in_range(int cur_n, int cur_m, int max_n, int max_m)
{
if (cur_n < 0 || cur_n >= max_n || cur_m < 0 || cur_m >= max_m)
return 0;
else
return 1;
}
void next(int *x, int *y, int dir)
{
switch (dir) {
case 0:
*x = *x - 1;
break;
case 1:
*y = *y + 1;
break;
case 2:
*x = *x + 1;
break;
case 3:
*y = *y - 1;
break;
case 4:
next(x, y, 0);
next(x, y, 1);
break;
case 5:
next(x, y, 0);
next(x, y, 3);
break;
case 6:
next(x, y, 2);
next(x, y, 1);
break;
case 7:
next(x, y, 2);
next(x, y, 3);
break;
}
}
void find(char *s, int n, int m)
{
int i, j, k;
int ci, cj;
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
for (k = 0; k < 8; k++) {
int t, flag = 0;
ci = i;
cj = j;
for (t = 0; t < strlen(s); t++) {
if (!in_range(ci, cj, n, m)) {
flag = 1;
break;
}
if (s[t] == tolower(a[ci][cj]) || s[t] == toupper(a[ci][cj])) {
next(&ci, &cj, k);
} else {
flag = 1;
break;
}
}
if (!flag) {
printf("%d %d\n", i + 1, j + 1);
return;
}
}
}
}
}
int main()
{
int r, c, i, t;
char s[50];
while (1) {
scanf("%d%d", &r, &c);
if (r == 0 && c == 0)
break;
for (i = 0; i < r; i++) {
memset(a[i], 0, 50);
scanf("%s", a[i]);
}
scanf("%d", &t);
while (t--) {
memset(s, 0, 50);
scanf("%s", s);
find(s, r, c);
}
printf("\n");
}
return 0;
}
```

Can we do better than this in complexity ?

DFS

- S O U N D W A V E February 24, 2014