Word Boggle [MEDIUM]

Company: Microsoft, MakeMyTrip, Google, Facebook, Directi, Amazon, Yahoo, Nvidia.

Question:

Given a dictionary, a method to do lookup in dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters. Note that we can move to any of 8 adjacent characters, but a word should not have multiple instances of same cell.

Example:

Input: dictionary[] = {"GEEKS", "FOR", "QUIZ", "GO"};
       boggle[][]   = {{'G','I','Z'},
                       {'U','E','K'},
                       {'Q','S','E'}};

Output:  Following words of dictionary are present
         GEEKS, QUIZ

Input:
The first line of input contains an integer T denoting the no of test cases . Then T test cases follow. Each test case contains an integer x denoting the no of words in the dictionary. Then in the next line are x space separated strings denoting the contents of the dictinory. In the next line are two integers N and M denoting the size of the boggle. The last line of each test case contains NxM space separated values of the boggle.

Output:
For each test case in a new line print the space separated sorted distinct words of the dictionary which could be formed from the boggle. If no word can be formed print -1.

Constraints:
1<=T<=10
1<=x<=10
1<=n,m<=7

Example:
Input:
1
4
GEEKS FOR QUIZ GO
3 3
G I Z U E K Q S E

Output:
GEEKS QUIZ

CODE:

import java.util.*;

import java.lang.*;

import java.io.*;

class GFG {

public static void main (String[] args) {

Scanner sc = new Scanner(System.in);

int t = sc.nextInt();

while(t-->0){

   GFG g = new GFG();

   int n,m,i,j;

   int len = sc.nextInt();

   String dictionary[] = new String[len];

   for(i=0;i<len;i++){

       dictionary[i] = sc.next();

   }

   

   n = sc.nextInt();

   m = sc.nextInt();

   

   char boggle[][] = new char[n][m];

   for(i=0;i<n;i++){

       for(j=0;j<m;j++){

           boggle[i][j] = sc.next().charAt(0);

       }

   }

   

   g.findwords(dictionary,n,m,boggle);

   System.out.println();

}

}

void findwords(String dictionary[],int n,int m,char boggle[][]){

   String str = "";

   TreeSet<String> mySet = new TreeSet<String>();

   int i,j;

   

        boolean visited[][] = new boolean[n][m];

        

   for(i=0;i<n;i++){

       for(j=0;j<m;j++){

           visited[i][j]=false;

       }

   }

   

   for(i=0;i<n;i++){

       for(j=0;j<m;j++){

           findPath(str,mySet,dictionary,boggle,i,j,visited,n,m);

       }

   }

   

   Iterator<String> itr=mySet.iterator();  

   if(mySet.isEmpty()){

       System.out.printf("-1");

   }

   else{

        while(itr.hasNext()){  

            System.out.printf("%s ",itr.next());

   }

    }

}

void findPath(String str,TreeSet<String> mySet,String dictionary[],char boggle[][],int i,int j,boolean visited[][],int n,int m){

   int a,k;

   visited[i][j]=true;

   str = str + boggle[i][j];

   

   for(a=0;a<dictionary.length;a++){

       if(str.equals(dictionary[a])){

           mySet.add(str);

       }

   }

   

   int rno[] = new int[]{-1,-1,-1,0,0,1,1,1};

   int cno[] = new int[]{-1,0,1,-1,1,-1,0,1};

   

   for(k=0;k<8;k++){

       if(isSafe(i+rno[k],j+cno[k],visited,n,m)){

           findPath(str,mySet,dictionary,boggle,i+rno[k],j+cno[k],visited,n,m);

       }

   }

   visited[i][j]=false;

}

boolean isSafe(int row,int col,boolean visited[][],int n,int m){

   if((row >= 0) && (row < n) &&

           (col >= 0) && (col < m) &&

            (!visited[row][col])){

               return true;

           }

                return false;

}

}