Leetcode: Word Search
This question is asked extremely commonly at both Amazon and Bloomberg. It is as follows:
Given an m x n grid of characters board and a string word, return true if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
An example is this, where we can "see" the word ABCCED.
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
And example 3 is looking for ABCB and there is nothing to be found as a result.
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
This problem is a 2D grid traversal problem, and the correct solution for this problem would be backtracking with depth-first search.
In backtracking, we mark the current path of exploration, and if this path doesn't lead up to a solution, we rever the change and backtrack, and then we try another path.
Walking along the 2D grid, at each step we mark a choice before jumping to the next step and end of each step we would revert as to try another direction. We should go as far as possible using the depth-first-search strategy before we try the next possible direction.
There's a certain formula that goes in relation to backtracking a problem:
First, we check if we reach the bottom case of the recursion where the word is empty, to see if a match for a prefix is found. We cog to check the number of characters
Then, we check if the current state is invalid, which means the position of the cell is out of bounds or the letter in the current cell does not match with the first letter of the word.
If the current step is valid, we will run DFS, marking the current cell as visited, and iterating up, right, down, and left, depending on preference. In the end, revert the cell back to its original state and return the result of the exploration.
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
self.board = board
self.ROWS = len(board)
self.COLS = len(board[0])
#backtrack every index to see if the word exists within the map
for row in range(self.ROWS):
for col in range(self.COLS):
if self.backtrack(row, col, word):
return True
return False
def backtrack(self, row, col, word):
#see if the word is empty and we have returned the characters
if len(word) == 0:
return True
#check the boundaries of the word see if out of bounds or not equivalent to word
if row < 0 or row == self.ROWS or col < 0 or col == self.COLS or self.board[row][col] != word[0]:
return False
ret = False
#mark the choice before exploring further
self.board[row][col] = '#'
#perform depth first search with up, down left, and right
for offRow, offCol in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
ret = self.backtrack(row + offRow, col + offCol, word[1:])
#we have found the word
if ret:break
#backtracking reverting step
self.board[row][col] = word[0]
return ret
Comments
Post a Comment