CareerCup

Please be more specific: are the elements that forms the word consecutive?

The solution to this question can only be obtained through brute force. There isn't any polynomial time algorithm for this as far as I know. NP-Complete You just have to try all possible words from the matrix and check with the dictionary.

dude for which position are you applying at Amazon??..Was that telephonic interview or inperson?

Here is my implementation to this question:

basicalgos.blogspot.com/2012/04/42-find-all-possible-words-from-2d.html

Can someone plz explain this more clearly "the valid words that can be formed using elements in a row, column and diagonal"?
e.g
C A E
T I N
B D K

what all words can be formed out of these?

Answer to an earlier (similar) questions on this site can be found at linearspacetime[dot] blogspot[dot]com

So heres the algorithm

First exemplify

Consider matrix

A. B. C.
D. E. F
G. H. I

Now simplify
//Make combination list
//Read row
// add each row to combination list
//Read column
// add each column to combination list
//Read diagonal
// add diagonal to combination list
// for each node in the combination list make permutations
//add each permutation to a hashtable as key and combination list node as value
// convert dictionary to a hash table
// for each permutation hash lookup hascode in dictionary
// if exists return true

I spent almost an hour to come up with below solution. could please give your feedback on solution.


Let us assume given matrix A[3][3] is

A N T
A I M
T O P

Also assume :: Is_word() check the string & print the string if it is a word

We need to check following strings start with A[0][0] (i.e A ) are words are not
Is_word ( "A[0][0]") ; // A[0][0] is A , first check, single letter could be a valid word
Case 1: Left to Right

AN , ANT

Case 2 : diagonal

AI , AIP

Case 3: Top to down
AA, AAT

similarly check following strings start with A[0][1] (i.e N ) are words are not

Is_word ( "A[0][1]") ; // A[0][1] is N ,first check, single letter could be a valid word
case 1: Left to right
NT
Case 2: diagonal
NM
case 3: top to down
NI , NIO

simlrly of other A[0][2], A[1][0] .... etc. location letters


Code for this problem is

Void Traverse_Matrix(char A[][], int n )
	{
		int i=0, j=0;

		char B[n];
		
		for (; i < n ; i++ )
		{
			for (; j< n ; j++ )
			{
				B[0] = A[i][j] ;
				Is_word(B, 1); // first check, single letter could be a valid word
				check_word(A,n,i,j+1,B,1,0); // left to right , last argument 0 specify , check left to right words
				check_word(A,n,i+1,j+1,B,1,1);// diagonal , last argument 1 specify , check diagonal words
				check_word(A,n,i+1,j,B,1,2);// left to right , last argument 0 specify , check all top to down words

			}
		}
	}

	void Check_word(char A[][], int n, int i, int j, char B[], int k, int direct )
	{
		if( i>= n || j>= n || k>=n )
		{
			return;
		}

		switch( direct )
		{
		case '0': B[k++] = A[i][j] ;
			      Is_word(B, k) ;
				  check_word(A,n,i,j+1,B,k,0); // left to right 
				  break;
		case '1': B[k++] = A[i][j] ;
			      Is_word(B, k) ;
				  check_word(A,n,i+1,j+1,B,k,1);// diagonal
				  break;
		case '2': B[k++] = A[i][j] ;
			      Is_word(B, k) ;
				  check_word(A,n,i+1,j,B,k,2);// top to down 
				  			  
		}
	}

Time complexity O(n^3) .


Please let me know if find any mistakes in my approach.