Find words in maze

Find words in a maze

We learned basics of tries in last post. Let’s see if we could apply some of those properties in solving some real problems. Today’ problem at hand is to find all the words which are present in a maze of characters of size NxN. The 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.

What is the brute force solution? Simple, find all the words which can be formed using these characters in maze starting of length 1 to N*N. For each word check if the given dictionary contains the word, if yes, store that word in the result.
What is the search space here? There will be (n2!) words to be looked into the dictionary. Not a practical solution. Optimizing search in the dictionary using sorting and binary search will not be of much help. (Good point to mention at interview though).
So how can we reduce the search space? Let’s first take an example and see what is happening in the brute force approach.
If we look closely, we are checking string length N, even though we already 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.

Store all words in the given dictionary in a trie. If there is no prefix in trie with length = i; there cannot be the word with i+1 length having this prefix of length i. So just abort the lookup of words with this prefix. Else increase the string length by 1 and repeat the above step. Trie fits perfectly in this algorithm as we are dealing with prefixes. We need to keep track that what we have already visited and if there can be more words with the visited prefix. If we take the example of the above maze, we start from ‘a’, as we see that there is no word starting with ‘a’ in trie by looking at children array of the root, we can safely avoid calculating words starting with ‘a’ of any length from there.

Find words in a maze : Implemenetation

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

#define N 4

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

   if(current->children[index] == NULL) 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;
     }
}


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 <N*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 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,i;
       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 main(){

        trie t;
        initialize(&t);
        int i;

        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(i =0; i <3; i++){
                insert(&t, dict[i]);
        }

         find_words_wrapper(&t, maze);
}

Even though we have reduced the search space, we may end up looking at all the words i.e (n2!). There is a way to reduce it by using dynamic method approach, we look at that in the future.