Leetcode: Word search
Given a two-dimensional array with english upper- and lowercase letters, named
board and a
True if the word appears on the board and false if not. We can go up, down, left, and right but not diagonal. Letters cannot be used twice.
When looking at this problem, it helps to imagine the
board as a tree. Every letter is a potential root of the tree, depending if it is equal to the start of the word that we are looking for. This allows us to apply a slightly modified version of the breadth-first-search algorightm (BFS).
Below is an example
board and the tree with a root at
A. Note that the
F on the second level is the same although it appears twice. This is important for the implementation later on. The tree is truncated and not shown completely.
Having this information, we can look at the implementation. First, a few helper variables are defined:
cols represent the number of rows and columns respectively. The
directions are the directions we can move on every step. It is easier to define them upfront in order to be able to loop over them and avoid large
if/else blocks. Lastly, we need an indication if a cell has been visited or not. This is because we can only visit each cell once.
We can then attempt to use every cell as the starting cell and recursively go to the next cell until either no letters in the word are remaining or until the next letter doesn’t match what is required. In this case we can abort and proceed differently.
After all options are exhausted, we go a step back and mark the current cell as no longer visited. If none of the paths yielded a valid result, we can return
Runtime: 8666 ms, faster than 28.73% of Python3 online submissions for Word Search. Memory Usage: 13.9 MB, less than 50.91% of Python3 online submissions for Word Search.