CareerCup

public class WordFinder
{
public static String[] getWordIndices(char[][] grid, String word)
{
// Assuming search in all directions is possible
int length = word.length(); // word length
String[] indices = new String[length]; // final indices
boolean found = false; // to indicate whether the word is found

for (int i = 0; i < grid.length; i++)
for (int j = 0; j < grid[0].length; j++)
{
// find 1st character in the word
if (grid[i][j] == word.charAt(0))
{
// check if vertical search is possible
if (i >= length - 1) // search up
{
found = true;
for (int k = 0; k < length; k++)
{
if (grid[i - k][j] == word.charAt(k))
indices[k] = (i - k) + "," + j;
else
{
found = false;
break;
}
}
if (found)
return indices;
}
if (grid.length - i >= length) // search down
{
found = true;
for (int k = 0; k < length; k++)
{
if (grid[i + k][j] == word.charAt(k))
indices[k] = (i + k) + "," + j;
else
{
found = false;
break;
}
}
if (found)
return indices;
}

// check if horizontal search is possible
if (j >= length - 1) // search left
{
found = true;
for (int k = 0; k < length; k++)
{
if (grid[i][j - k] == word.charAt(k))
indices[k] = i + "," + (j - k);
else
{
found = false;
break;
}
}
if (found)
return indices;
}
if (grid.length - j >= length) // search right
{
found = true;
for (int k = 0; k < length; k++)
{
if (grid[i][j + k] == word.charAt(k))
indices[k] = i + "," + (j + k);
else
{
found = false;
break;
}
}
if (found)
return indices;
}

// check if diagonal search is possible
if (i >= length - 1 && j >= length - 1) // search up left
{
found = true;
for (int k = 0; k < length; k++)
{
if (grid[i - k][j - k] == word.charAt(k))
indices[k] = (i - k) + "," + (j - k);
else
{
found = false;
break;
}
}
if (found)
return indices;
}

// search up right
if (i >= length - 1 && grid.length - j >= length)
{
found = true;
for (int k = 0; k < length; k++)
{
if (grid[i - k][j + k] == word.charAt(k))
indices[k] = (i - k) + "," + (j + k);
else
{
found = false;
break;
}
}
if (found)
return indices;
}

// search down left
if (grid.length - i >= length && j >= length - 1)
{
found = true;
for (int k = 0; k < length; k++)
{
if (grid[i + k][j - k] == word.charAt(k))
indices[k] = (i + k) + "," + (j - k);
else
{
found = false;
break;
}
}
if (found)
return indices;
}

// search down right
if (grid.length - i >= length && grid.length - j >= length)
{
found = true;
for (int k = 0; k < length; k++)
{
if (grid[i + k][j + k] == word.charAt(k))
indices[k] = (i + k) + "," + (j + k);
else
{
found = false;
break;
}
}
if (found)
return indices;
}

}
}
return null;
}

public static void main(String[] args)
	{
		char[][] grid = { 
				{ 'a', 'b', 'c', 'd' }, 
				{ 'e', 'f', 'g', 'h' },
				{ 'i', 'j', 'k', 'l' }, 
				{ 'm', 'n', 'o', 'p' } };

		String[] indices = getWordIndices(grid, "oje");
		if (indices != null)
			for (String index : indices)
				System.out.println(index);
	}
}

for example: the given matrix is of 4x4
s i l k
u i i i
l t n c
k s k k

Now, we have to found "nil"
Iterate the matrix in any manner (row-wise or column-wise), whenever you get the first element which is equal to first letter of word
then reduce the size of matrix. In this example, If we iterate the matrix, then we found "n" at (2,2). Now take two matrix, in one matrix
"n" will be last element and in another it will be first element. Like, after reduction the matrix will be

s i l
u i i
l t n

NOTE: the size of matrix will be mxm. Here m is the size of string to be searched.
Now match each row (right to left), column(bottom to top), diagonal(bottom to top) in reverse direction because here "n" is the last element.

And other matrix
n c null
k k null
null null null

This matrix contains null or beyond the size of matrix. So you can ignore it.

class Program
    {
        private static List<KeyValuePair<int, int>> SearchWord(char[,] matrix, string word)
        {
            var foundWord = new List<KeyValuePair<int, int>>();
            string reverseWord = String.Join("", word.Reverse());
            for (int i = 0; i < matrix.GetLength(0); ++i)
            {
                for (int j = 0; j < matrix.GetLength(1); ++j)
                {
                    if (matrix[i, j] == word[0])
                    {
                        if (matrix.GetLength(1) - j + 1 > word.Length &&
                            MatchWordHorizontal(matrix, new KeyValuePair<int, int>(i, j), word, foundWord))
                        {
                            return foundWord;
                        }

                        if (matrix.GetLength(0) - i + 1 > word.Length &&
                            MatchWordVertical(matrix, new KeyValuePair<int, int>(i, j), word, foundWord))
                        {
                            return foundWord;
                        }

                        if (matrix.GetLength(0) - i + 1 > word.Length &&
                            matrix.GetLength(1) - j + 1 > word.Length &&
                            MatchWordDiagonal(matrix, new KeyValuePair<int, int>(i, j), word, foundWord))
                        {
                            return foundWord;
                        }
                    }
                    else if (matrix[i, j] == reverseWord[0])
                    {
                        if (matrix.GetLength(1) - j + 1 > reverseWord.Length &&
                            MatchWordHorizontal(matrix, new KeyValuePair<int, int>(i, j), reverseWord, foundWord))
                        {
                            return foundWord;
                        }

                        if (matrix.GetLength(0) - i + 1 > reverseWord.Length &&
                            MatchWordVertical(matrix, new KeyValuePair<int, int>(i, j), reverseWord, foundWord))
                        {
                            return foundWord;
                        }

                        if (matrix.GetLength(0) - i + 1 > reverseWord.Length &&
                            matrix.GetLength(1) - j + 1 > reverseWord.Length &&
                            MatchWordDiagonal(matrix, new KeyValuePair<int, int>(i, j), reverseWord, foundWord))
                        {
                            return foundWord;
                        }
                    }
                }
            }

            return null;
        }

        private static bool MatchWordHorizontal(char[, ] matrix, KeyValuePair<int, int> startingCell, string word, List<KeyValuePair<int, int>> foundWord)
        {
            foundWord.Clear();
            for (int i = 0; i < word.Length; ++i)
            {
                if (matrix[startingCell.Key, startingCell.Value + i] != word[i])
                {
                    return false;
                }

                foundWord.Add(new KeyValuePair<int, int>(startingCell.Key, startingCell.Value + i));
            }

            return true;
        }

        private static bool MatchWordVertical(char[, ] matrix, KeyValuePair<int, int> startingCell, string word, List<KeyValuePair<int, int>> foundWord)
        {
            foundWord.Clear();
            for (int i = 0; i < word.Length; ++i)
            {
                if (matrix[startingCell.Key + i, startingCell.Value] != word[i])
                {
                    return false;
                }

                foundWord.Add(new KeyValuePair<int, int>(startingCell.Key + i, startingCell.Value));
            }

            return true;
        }

        private static bool MatchWordDiagonal(char[,] matrix, KeyValuePair<int, int> startingCell, string word, List<KeyValuePair<int, int>> foundWord)
        {
            foundWord.Clear();
            for (int i = 0; i < word.Length; ++i)
            {
                if (matrix[startingCell.Key + i, startingCell.Value + i] != word[i])
                {
                    return false;
                }

                foundWord.Add(new KeyValuePair<int, int>(startingCell.Key + i, startingCell.Value + i));
            }

            return true;
        }

        static void Main(string[] args)
        {
            char[,] matrix = new char[3, 3]
                              {
                                  {'a', 'b', 'c'},
                                  {'x', 'y', 'z'},
                                  {'l', 'm', 'n'}
                              };

            List<string> wordsToSearch = new List<string>() {"ayn", "by", "zy"};

            foreach (var word in wordsToSearch)
            {
                var foundWord = SearchWord(matrix, word);
                if (foundWord != null)
                {
                    Console.WriteLine("Found word {0} at {1}.", word, String.Join(",", foundWord));
                }
            }
        }
    }

class Coordinate{
	private int row;
	private int col;
}

ArrayList<Integer> findWord(char[][] grid, int N, String word){
	ArrayList<Integer> index = new ArrayList<Integer>();
	for(int r = 0; r < N-1; r++){
		for(int c = 0; c<N-1; c++){
			if(word.charAt(0) == grid[r][c]){
				index = searchWord(grid, r, c, N, word);
				if(index != null)
					break;
			}
		}
	}
	return index;
}

Coordinate searchWord(char[][] grid, int r, int c, int N, String word){
	//search vertically
	if(r + word.length()-1 < N-1){
		ArrayList<Coordinate> index = new ArrayList<Coordinate>();
		for(int i=0, i<word.length();i++, r++){
			if(word.charAt(i) != grid[r][c])
				break;
			index.add(new Coordinate(r,c));
		}
		if(index.size() == word.length())
			return index;
	}
	//search horizontally
	if(c + word.length()-1 < N-1){
		ArrayList<Coordinate> index = new ArrayList<Coordinate>();
		for(int i=0, i<word.length();i++, c++){
			if(word.charAt(i) != grid[r][c])
				break;
			index.add(new Coordinate(r,c));
		}
		if(index.size() == word.length())
			return index;
	}
	//search diagonally
	if(r + word.length()-1 < N-1 && c + word.length()-1 < N-1){
		ArrayList<Coordinate> index = new ArrayList<Coordinate>();
		for(int i=0, i<word.length();i++, c++, r++){
			if(word.charAt(i) != grid[r][c])
				break;
			index.add(new Coordinate(r,c));
		}
		if(index.size() == word.length())
			return index;
	}
	return null;
}

DFS traversal would serve the purpose for this problem

import java.util.*;
class WordFindMatrix {
	public static int[] dx = {-1,-1,0,1,1,1,0,-1};
	public static int[] dy = {0,1,1,1,0,-1,-1,-1};
	
	public static boolean isValid(char[][] mat,boolean[][]isVisited,int m, int n,int a, int b,int x, int y, String word, int i)
	{
		if (x<0||y<0||x>=m||y>=n||isVisited[x][y]==true||word.charAt(i)!=mat[x][y]) return false;
		return true;
	}
	
	public static void dfs(char[][] mat, String word,int r,int c,ArrayList <Integer> l)
	{
		boolean[][] isVisited=new boolean[r][c];
		for (int i=0;i<r;i++)
			for (int j=0;j<c;j++)
				isVisited[i][j]=false;	
		
		for (int i=0;i<r;i++)
			for (int j=0;j<c;j++)
				if (mat[i][j]==word.charAt(0))
					if(dfsHelper(mat,isVisited,word,0,i,j,r,c,l)==true) return;
	}
	
	public static boolean dfsHelper(char[][] mat,boolean[][]isVisited,String word, int index,int x,int y, int r, int c,ArrayList<Integer>l)
	{
		if(index+1 == word.length()){l.add(x);l.add(y); return true;}
		for (int i=0;i<8;i++){
			l.add(x);
			l.add(y);
			isVisited[x][y]=true;
			if(isValid(mat,isVisited,r,c,x,y,x+dx[i],y+dy[i],word,index+1)==true){
			if (dfsHelper(mat,isVisited,word,index+1,x+dx[i],y+dy[i],r,c,l)==true) return true;
			}
			l.remove(l.size()-1);
			l.remove(l.size()-1);
			isVisited[x][y]=false;

		}
		return false;
		
	}
	
	public static void main(String[] args) {
		char mat[][]={{'a','b','i','a'},{'d','n','i','m'},{'i','n','a','e'},{'a','n','v','p'}};
		String wordToSearch = "aibnnnvp";
		ArrayList <Integer> l = new ArrayList<Integer>();
		dfs(mat,wordToSearch,mat.length,mat[0].length,l);
		
		for (int i=0;i<l.size();i=i+2)
			System.out.print("("+l.get(i)+","+l.get(i+1)+")"+"-->");
	}

}

Hi, Mahamoud,
I think yoyr code looks perfect except, for the diagonal search of word the condition sjould be checked with Length/(√2). As the diagonal match can occur when the coordinates are even at (length/√2, length/√2)