Friedrich Ewald My Personal Website

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
                            ...  ...  ...
Having this information, we can look at the implementation. First, a few helper variables are defined: 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
      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
      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.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.