LeetCode 79. Word Search

Description

https://leetcode.com/problems/word-search/

Given a 2D board and a word, find if the word exists in the grid.

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

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Constraints:

  • board and word consists only of lowercase and uppercase English letters.
  • 1 <= board.length <= 200
  • 1 <= board[i].length <= 200
  • 1 <= word.length <= 10^3

Explanation

The solution would be backtracking, which is a methodology where we mark the current path of exploration, if the path does not lead to a solution, we then revert the change (i.e. backtracking) and try another path.

As the general idea for the solution, we would walk around the 2D grid, at each step we mark our choice before jumping into the next step. And at the end of each step, we would also revert our marking, so that we could have a clean slate to try another direction. In addition, the exploration is done via the DFS strategy, where we go as further as possible before we try the next direction.

Python Solution

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if (len(board) == 0 or len(board[0]) == 0):
            return False
        
        for i in range(0, len(board)):
            for j in range(0, len(board[0])):
                if self.helper(board, i, j, word):
                    return True
        return False
        
        
    def helper(self, board, i, j, word):
        if len(word) == 0:
            return True
        
        if i < 0 or i > len(board) - 1 or j < 0 or j > len(board[0]) - 1:
            return False
        
        if board[i][j] != word[0]:
            return False
        
        char = board[i][j]
        board[i][j] = '#'        
        
        suffix = word[1:]
        result = self.helper(board, i + 1, j, suffix) or self.helper(board, i - 1, j, suffix) or self.helper(board, i, j + 1, suffix) or self.helper(board, i, j - 1, suffix)
        
        board[i][j] = char

        return result
  • Time complexity: O(N * 4^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, its execution trace would be visualized as a 4-ary tree, each of the branches represent a potential exploration in the corresponding direction. Therefore, in the worst case, the total number of invocation would be the number of nodes in a full 4-nary tree, which is about 4^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 * 4^L).
  • Space complexity: O(L). where L is the length of the word to be matched.

One Thought to “LeetCode 79. Word Search”

Leave a Reply

Your email address will not be published. Required fields are marked *