LeetCode: Word Search in 2D Matrix of characters

Difficulty Level: $\mathtt{MEDIUM}$
This is a LeetCode question. Find the DESCRIPTION HERE

Solution

This problem can be solved using Depth First Search (DFS) which will employ necessary Backtracking. Starting from any cell, we look for a match of characters from the beginning of input word. If there is a match, we look for the next character in the input word in the neighboring unvisited cells of the board. When the whole word is found, we return true.

Backtracking

When there is a match for a character in a word, we move to next character and also move to next neighbor. For the given cell there are Four possible neighbors. At a time, we select one neighbor and expand the search. It can happen that one neighbor might lead to a path where only some characters are matched while other neighbor can lead to the path where whole word is matched. So if we select the first neigbor, it will ultimately lead the end where we don't have any match. At such time, we should be able to backtrack and follow different path to look for possible desirable path.

Implementation

Following is the implemenation of the backtracking solution using DFS discussed above.

Time Complexity

The exist() method runs two loops for $row \times column$ times and the dfs() method can also run upto $row \times column$ times.
$\therefore$ The complexity of this approach is $\cal{O(mn)^2}$ where $m\ = \ number\ of\ rows$ and $n\ = \ number\ of\ columns$.

Space Complexity

Here we are using extra 2D matrix visited to keep track of cells which are already visited.
$\therefore$The space complexity is $\cal{O(mn)}$.
This can be reduced to $\cal{O(1)}$ by modifying the input board to update each character with special character to mark that it has been visited. The modified character can be reset afterwards.

---

---

---