Katkat
Back

Determine Whether a Word Exists in a Graph

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests the ability to implement a depth-first search (DFS) with backtracking to find a specific sequence within a grid, while managing state to avoid reusing the same path.

Problem Statement

Given an m x n grid of characters and a string word, write a function to determine if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a single word.

Function Signature

def exist(board: List[List[str]], word: str) -> bool:

Constraints

  • m == len(board)
  • n == len(board[i])
  • 1 <= m, n <= 6
  • 1 <= len(word) <= 15
  • board and word consist of only lowercase and uppercase English letters.

Examples

Example 1: Input: board = [['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], word = "ABCCED" Output: True Explanation: The path is A -> B -> C -> C -> E -> D.

Example 2: Input: board = [['A','B'], ['C','D']], word = "ABCD" Output: False

Edge Cases

  • Single cell grid.
  • Word longer than the total number of cells.
  • Repeated characters in the word.
  • Grid containing only one type of character.

Hints

Hint 1

Start a search from every cell in the grid that matches the first letter of the word.

Hint 2

Use recursion (DFS) to explore the four possible directions (up, down, left, right) from the current cell.

Hint 3

Temporarily mark the visited cells during recursion to prevent re-using them in the current path, and unmark them (backtrack) once the recursive call returns.

Follow-up questions

  • How would you modify your solution if the word could be formed using diagonal movements as well?
  • What is the time complexity of your approach in the worst-case scenario?
  • Can this problem be solved using a Trie or BFS? Why or why not?