3. Develop an algorithm to be able to do the word search. Write the algorithm in

Question

3. Develop an algorithm to be able to do the word search. Write the algorithm in pseudocode. The word search starts with an nxn square of letters (n rows and n columns stored in an nxn two- dimensional array) and a given word to search. You should search vertically (up/down) and horizontally (left/right) (omit searching diagonally for simplicity) starting from the first letter in the two- dimensional array, continue until either the word is found or the end of the array is reached. You may need to use a stack to help remember which direction has been checked, which has not. The result has to be saved.

Explanation / Answer

This question can be solved using Depth First Seach algorithm.
In case you are not familiar with with DFS, it works in the following manner:
Depth First Search (DFS) algorithm traverses a graph in a depthward motion, that is, it starts from a root node and explores it's entire branch before backtracking to pick a new node to explore. It uses a stack to remember to get the next vertex to start a search.

In this problem, we apply DFS on each occurence of first character of the word in the matrix. Unlike standard DFS, where we recursively call for all adjacent vertices, here we call for 4 adjacent vertices only (top, bottom, left and right).

The pseudocode for the problem is as follows:

isValid(row, column, prevRow, prevColumn)
return (row >= 0) && (row < N) &&(column >= 0) && (col < N) &&!(row== prevRow && column == prevColumn)

rowNum[] = {0, 0, 1, -1}
colNum[] = {-1, 1, 0, 0}

DFS(matrix[N][N], row, column, prevRow, prevColumn, word, result, index, lengthOfWord)
  if (index > lengthOfWord || matrix[row][column] != word[index])
  return

result+="(" + row + "," + column + ")"

if (index == lengthOfWord)
  print result
  return

for k<4
if (isvalid(row + rowNum[k], column + colNum[k],prevRow, prevColumn))
DFS(matrix, row + rowNum[k], column + colNum[k], row, column, word, result, index+1, lengthOfWord)   

findWordInMatrix(matrix[N][N], word, lengthOfWord)
for (i=0; i<N; i++)
for(j=0; j<N; j++)
if(matrix[i][j] == word[0])
DFS(matrix, i, j, -1, -1, word, " ", 0, lengthOfWord)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.