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

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

      }

  }

}