Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Word Search (medium)

Problem Statement

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.

Example 1:

  • Input: word="ABCCED", board:

      { 'A', 'B', 'C', 'E' },
  { 'S', 'F', 'C', 'S' },
  { 'A', 'D', 'E', 'E' }

  • Output: true

  • Explanation: The word exists in the board:
    -> { 'A', 'B', 'C', 'E' },

.....

.....

.....

Like the course? Get enrolled and start learning!
G

greenwald.juj

· 3 years ago

Problem Statement: 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.

Solution: The basic approach to solving the word search problem using backtracking is to start at the first character of the word and check all 8 adjacent cells in the grid to see if any of them match the next character of the word. If a match is found, mark the cell as visited and recursively check the next character of the word in the adjacent cells of the newly visited cell. If the entire word is found, return true. If no match is found, backtrack to t

Show 1 reply
cogom

cogom

· 3 years ago

Could you explain why the time complexity will be O(4^n), not O(m * n * 4^n)? The recursive dfs functions will indeed take O(4^n), but I thought we call it m * n times in the extreme case.. Thank you in advance!

Show 1 reply
S

Shane

· 3 years ago

This was nice! I love it.

Added that line right before calling the dfs function to ensure it only checks for a word if it begins with the correct letter.

if(!(board[i][j] == word[0])) continue
Arturo Calderón

Arturo Calderón

· 3 years ago

Marking the current cell (see line 10 of the solution) does nothing, as it is never checked, nor does it change the result if omitted.

Are we really solving this with backtracking?

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def exist(self, board, word):

    def get_neighbors(loc):
      alpha_rows = [0, 1, 0, -1]
      alpha_cols = [1, 0, -1, 0]
      neighbors = []
      for i in range(len(alpha_rows)):
        row = loc[0] + alpha_rows[i]
        col = loc[1] + alpha_cols[i]
        if row >= 0 and row < len(board) and col >=0 and col < len(board[row]):
          neighbors.append((row, col))
      return neighbors
   
    def dfs(loc, seen, index):
      if board[loc[0]][loc[1]] != word[index]:
        return False 
        
      if index == len(word) - 1:
        return True

      for neighbor in get_neighbors(loc):
        if neighbor not in seen:
          seen.add(neighbor)
          if dfs(neighbor, seen, index + 1):
            return True

      return False

    fo