Word Search in a 2d matrix using DFS & backpropagation

Problem Statement 🙋‍♂️

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighbouring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters.

Intuition 🤔

We can go over each element in the grid by using a simple traversal and for each cell, we can call a DFS function which will check if starting from that r,c cell, if the searchword is found. If it’s found, then we can return true and else continue to search for the next cell pair. If no match is found and we have reached the end of our traversal of the 2D matrix, then return False

Such a DFS function will accept 3 parameters:

• Current row id
• Current column id
• Id of word character we want to find

The function will first check for the valid case which is when the word is found. We check if we reach the bottom case of the recursion, where the word to be matched is empty, i.e. we have already found the match for each prefix of the word. We can check this by checking if the ith character is equal to the length of the word to be matched. In such a case, return True

Then it will return False for any invalid cases, some of these invalid cases are:

• The values of r and c are out of bounds
• The i^th character we are looking for has not been found on the board
• This r,c (representing a cell) was already visited

Later, we then start the exploration of backtracking with the strategy of DFS. First, we mark the current cell as visited, e.g. any non-alphabetic letter will do. Then we iterate through the four possible directions, namely up, right, down and left. The order of the directions can be altered, to one’s preference. If any of the four immediate neighbours (left, right, top or bottom) is true then we will return True else we will backtrack

At the end of the exploration, we revert the cell back to its original state.

After we have called DFS function for every pair of r,c and still not got an True return, it means we have not found the word, so return False

Time and Space Complexity

Special credits to the Leetcode solution section to explaining TC and SC

Time Complexity: O(N⋅ 3^L) where N is the number of cells in the board and L is the length of the word to be matched.

• For the backtracking function, initially, we could have at most 4 directions to explore, but further, the choices are reduced into 3 (since we won’t go back to where we come from). As a result, the execution trace after the first step could be visualized as a 3-ary tree, each of the branches representing a potential exploration in the corresponding direction. Therefore, in the worst case, the total number of invocations would be the number of nodes in a full 3-nary tree, which is about 3^L
• We iterate through the board for backtracking, i.e. there could be N times invocation for the backtracking function in the worst case.
• As a result, overall the time complexity of the algorithm would be O(N⋅3^L)

Space Complexity: O(L) where L is the length of the word to be matched. The main consumption of the memory lies in the recursion call of the backtracking function. The maximum length of the call stack would be the length of the word. Therefore, the space complexity of the algorithm is O(L)

Let’s code it up 👨🏻‍💻

For more such solutions clone https://github.com/amarjitdhillon/CP_2021 repo. For questions, please comment on the Gist

Make sure you try to solve this question on your own after you understand the logic 😀

Have a good one!