Search a Word in a 2D Grid of characters (Word Search)

Given a 2D grid of characters and a single word/an array of words, find all occurrences of the given word/words in the grid. A word can be matched in all 8 directions at any point. Word is said to be found in a direction if all characters match in this direction (not in zig-zag form).
The 8 directions are, Horizontally Left, Horizontally Right, Vertically Up, Vertically Down and 4 Diagonal directions.

Example: 

Input:  grid[][] = {"GEEKSFORGEEKS",
                    "GEEKSQUIZGEEK",
                    "IDEQAPRACTICE"};
        word = "GEEKS"

Output: pattern found at 0, 0
        pattern found at 0, 8
        pattern found at 1, 0
Explanation: 'GEEKS' can be found as prefix of
1st 2 rows and suffix of first row

Input:  grid[][] = {"GEEKSFORGEEKS",
                    "GEEKSQUIZGEEK",
                    "IDEQAPRACTICE"};
        word = "EEE"

Output: pattern found at 0, 2
        pattern found at 0, 10
        pattern found at 2, 2
        pattern found at 2, 12
Explanation: EEE can be found in first row 
twice at index 2 and index 10
and in second row at 2 and 12

Below diagram shows a bigger grid and presence of different words in it. 

Source: Microsoft Interview Question.
 

Approach when a single word is given: The idea used here is simple, we check every cell. If cell has first character, then we one by one try all 8 directions from that cell for a match. Implementation is interesting though. We use two arrays x[] and y[] to find next move in all 8 directions. 
Below are implementation of the same:  

pattern found at 0, 0
pattern found at 0, 8
pattern found at 1, 0

pattern found at 0, 2
pattern found at 0, 10
pattern found at 2, 2
pattern found at 2, 12

Complexity Analysis:  

• Time complexity: O(R*C*8*len(str)). 
  All the cells will be visited and traversed in all 8 directions, where R and C is side of matrix so time complexity is O(R*C).
• Auxiliary Space: O(1). 
  As no extra space is needed.

Approach when array of words is given: The idea used here is simple, we check every cell. If cell has first character, then we one by one try all 8 directions from that cell for a match, put this check in a loop.  We use mover array to store the manner in which next moves are possible={left,right,up,down,…diagonals}. 
Below are implementation of the same:  

oath->{0,0}
eat->{1,0}
eat->{1,3}

Complexity Analysis:  

• Time complexity: O(R*C*len(str)*Number(str)*len(str)). 
  All the cells will be visited and traversed in all 8 directions, where R and C is side of matrix so time complexity is O(R*C) for each string.
• Auxiliary Space: O(R*C*Numberof(str)*len(str)). (due to visited array)

Another Approach:

The code implements a solution class that takes a board of characters and a list of words as input. It then performs a depth-first search to find if the words are present on the board. If a word is found, it is added to the output along with its position on the board. The code uses a visited array to keep track of the cells that have been visited during the search. Finally, the function returns a vector of strings, where each string is a word followed by its position on the board.

Implementation is given below:

['oath -> {0,0}', 'eat -> {1,0}', 'eat -> {1,3}']

The time complexity of the findWords function is O(N * M * L * 8^L), where N is the number of rows in the board, M is the number of columns in the board, L is the maximum length of the word in the dictionary. For each starting point on the board, the algorithm may explore up to 8 directions, and at each step, it needs to check if the next letter in the word matches the character in the board. Since the maximum length of the word is L, this gives a factor of L in the time complexity.

The space complexity of the algorithm is O(N * M + L), where N and M are the dimensions of the board, and L is the length of the longest word in the dictionary. The space is used to store the visited array, which has the same size as the board, and the recursion stack, which can be as deep as the length of the longest word in the dictionary.

Exercise: The above solution only print locations of word. Extend it to print the direction where word is present.
See this for solution of exercise.
This article is contributed by Utkarsh Trivedi. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.