Leetcode: Word search
Given a two-dimensional array with english upper- and lowercase letters, named board and a word, return 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.
+---+---+---+---+ A
|(A)| B | C | E | / \
| S | F | C | S | S B
| A | D | E | E | / \ / \
+---+---+---+---+ F A F C
... ... ...rows, 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 False.
from typing import List
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
rows = len(board)
cols = len(board[0])
directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
visited = set()
def dfs(idx, x, y):
if board[x][y] != word[idx]:
return False
if board[x][y] == word[idx] and idx == len(word) - 1:
return True
visited.add((x,y))
for d in directions:
new_x = x + d[0]
new_y = y + d[1]
if new_x in range(rows) and new_y in range(cols) and (new_x, new_y) not in visited:
if dfs(idx+1, new_x, new_y):
return True
visited.remove((x,y))
return False
for x in range(rows):
for y in range(cols):
if dfs(0, x, y):
return True
return False
if __name__ == '__main__':
s = Solution().exist
print(s([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED"), True)
print(s([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "SEE"), True)
print(s([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCB"), False)
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.