# Find words in matrix

Please refer Trie data structure to read more about tries as that would be pre-requisite to solve ‘words in matrix problem’. Problem at hand is to find words in matrix of letters. Size of matrix is MxN. Condition is that characters of words should be adjacent to each other either horizontally or vertically.
For example, below maze contains cat, dog and word words in it.

## Words in matrix : Trie solution

What is the brute force solution? Simple, find all words which can be formed using characters in matrix starting of length 1 to N*N. For each word, check if given dictionary contains the word, if yes, store that word in result.

What is search space here? There will be (N*N)! words to look into dictionary. Not a practical solution. Optimizing search in dictionary using sorting and binary search will not be of much help. (Good point to mention at interview though).

So, how can we reduce search space. Let’s first take an example and see what is happening in brute force approach. We are checking string length N, even though we know that N-1 character string leading to it is not a valid string. Can we avoid it? Yes, using tries. This is how we can do it.

```1. Store all words in given dictionary in a trie.
2. If there is no prefix in trie with length = i; there cannot be word with i+1 length having this prefix of length i. So just abort the look up of words with this prefix.
3. Else increase string length by 1 and repeat step 2.
```

Trie fits perfectly in algorithm as we deal with prefixes. Keep track that what we have already visited and if there can be more words with the visited prefix.

If we take example of above matrix, start from ‘a’, as there is not word starting with ‘a’ in trie by looking at children array of root, avoid calculating words starting with ‘a’ of any length from there.

## Words in matrix implementation

```#include<stdio.h>
#include<stdlib.h>

#define N 4

#define MAX_SIZE 26

#define GET_CHAR_INDEX(ch)\
((int) ch - (int)'a' )

#define LEAF_NODE  1
#define true 1
#define false 0

typedef struct trie_node_t {
int value;
struct trie_node_t * children[MAX_SIZE];
}Node;

typedef struct trie{
int count ;
Node *root;
}trie;

void initialize(trie *t){
t->root = (Node *)malloc(sizeof(Node));
t->count =0;
}

void insert(trie *t, char key[]){

int len = strlen(key);
int i;

if(!(t->root)){
printf("\n Trie is not initialized\n");
}

Node * current = t->root;
for(i=0; i<len; i++){

/* Get the index of char in children array */
int index  =  GET_CHAR_INDEX(key[i]);

/* If the children array does not contain the pointer
at index pointed by char, allocate new node */

if(!(current->children[index]) ){
current->children[index] = (Node *)malloc(sizeof(Node));
}
/* Else traverse down the trie. */
current = current->children[GET_CHAR_INDEX(key[i])];
}

/* To mark it as leaf */
current->value = LEAF_NODE;
}

int search_key(Node *current, char key){
int index  =  GET_CHAR_INDEX(key);

if(!(current->children[index]) ) return false;

return true;
}

enum direction {
NORTH =1,
SOUTH,
LEFT,
RIGHT
};

void update_params(int row, int col, int *new_row,
int *new_col, int dir){
switch(dir){
case NORTH:
*new_row = --row;
*new_col = col;
break;
case SOUTH:
*new_row = ++row;
*new_col = col;
break;
case LEFT:
*new_col =  ++col;
*new_row = row;
break;
case RIGHT:
*new_col =  --col;
*new_row = row;
break;
}
}
int valid_position(int row, int col){
if(row<0 || row>N-1 || col <0 || col>N-1) return false;

return true;
}

int find_words(Node *t, char maze[][N], int curr_len,
int curr_row, int curr_col, int *prefix){

int new_row, new_col;
int  dir;
char key = maze[curr_row][curr_col];

Node * current = t->children[GET_CHAR_INDEX(key)];

/* Before finish the prefix we hit the null,
prefix is not present */
if(current == NULL) return false;

/* If reach the prefix of len = curr_len but its not a word,
we can look forward with len = curr_len +1 */
if(curr_len == 1 && current->value != LEAF_NODE){
*prefix = true;
return false;
}
/* If we reach at the leaf node, for this length,
we found a word with length = curr_len */
if(curr_len == 1 && current->value == LEAF_NODE)
return true;

/* For every character look in all direction */
for(dir = NORTH; dir<= RIGHT; dir++){

/* if the key is present */
if(search_key(t, key)){
/* Move to next character based on direction of movement */
update_params(curr_row, curr_col, &new_row, &new_col, dir);

/*Validate that we are good in maze */
if(valid_position(new_row, new_col)){

/*Find word with len -1 in remaining trie */
if(find_words(current, maze, curr_len-1,
new_row, new_col, prefix)) {
return true;
}
}
}
else{
return false;
}
}
}

void find_words_wrapper(trie *t, char maze[][N]){

int i,j,len, prefix_found = false;
for(i=0; i<N; i++){
for(j=0; j<N; j++){

/*Consider all length words which can be formed
stating with maze[i][j] char */

for(len =1; len <2*N; len++){
/* To check if we need to check for further length
1. if prefix_found = false, don't check,
no words possible for larger length
2. if prefix_found = true, continue looking*/

prefix_found = false;

/* If finally reached at the leaf of trie starting
with maze[i][j] and length = len */

if(find_words(t->root, maze, len,i,j, &prefix_found)){
printf(" Word found at (%d %d)\n", i,j);
}
else if(prefix_found == false)
break;
}
}
}
}

int main(){

trie t;
initialize(&t);

char *dict []  = {"cat", "dog", "word"};

char maze[N][N]  = { 'a' , 'c', 'a', 't',
'd' , 'w', 'o', 'r',
'o',  'g', 'd', 'd',
'p', 'p',  'p', 'p'
} ;
for(int i =0; i <3; i++){
insert(&t, dict[i]);
}

find_words_wrapper(&t, maze);

return 0;
}
```