Answer:
import java.util.*;
public class Main {
public static String[] wordSearch(char[][] matrix, String[] words) {
int N = matrix.length;
List<String> myList = new ArrayList<String>();
int pos = 0;
for(String word : words)
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (search(matrix, word, i, j, 0, N)) {
if(!myList.contains(word))
{
myList.add(word);
}
}
}
}
}
String[] newDict = myList.toArray(new String[myList.size()]);
return newDict;
}
public static boolean search(char[][] matrix, String word, int row, int col,
int index, int N) {
// check if current cell not already used or character in it is not not
if (word.charAt(index) != matrix[row][col]) {
return false;
}
if (index == word.length() - 1) {
// word is found, return true
return true;
}
// check if cell is already used
if (row + 1 < N && search(matrix, word, row + 1, col, index + 1, N)) { // go
// down
return true;
}
if (row - 1 >= 0 && search(matrix, word, row - 1, col, index + 1, N)) { // go
// up
return true;
}
if (col + 1 < N && search(matrix, word, row, col + 1, index + 1, N)) { // go
// right
return true;
}
if (col - 1 >= 0 && search(matrix, word, row, col - 1, index + 1, N)) { // go
// left
return true;
}
if (row - 1 >= 0 && col + 1 < N
&& search(matrix, word, row - 1, col + 1, index + 1, N)) {
// go diagonally up right
return true;
}
if (row - 1 >= 0 && col - 1 >= 0
&& search(matrix, word, row - 1, col - 1, index + 1, N)) {
// go diagonally up left
return true;
}
if (row + 1 < N && col - 1 >= 0
&& search(matrix, word, row + 1, col - 1, index + 1, N)) {
// go diagonally down left
return true;
}
if (row + 1 < N && col + 1 < N
&& search(matrix, word, row + 1, col + 1, index + 1, N)) {
// go diagonally down right
return true;
}
// if none of the option works out, BACKTRACK and return false
return false;
}
public static void main(String[] args) {
char[][] matrix = { { 'j', 'a', 's' },
{ 'a', 'v', 'o'},
{ 'h', 'a', 'n'} };
String[] arr_str = {"a", "java", "vaxn", "havos", "xsds", "man"};
arr_str = wordSearch(matrix, arr_str);
for(String str : arr_str)
{
System.out.println(str);
}
}
}
