Question

Given an N x M matrix and a dictionary containing K distinct words of length between 1 and 30 symbols, the Word Search should return all the words you can get from the matrix that are contained in the dictionary. There are rules: You can start from any cell in the matrix and go up, down, to the left, and to the right (not leaving the matrix) to collect letters for the word. Your "path" should not cross itself, i.e., a cell in the matrix cannot be visited more than once. You need to return the array of words found. There is no need to return the "paths" for them.

Answer 1

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);

}

}

}