Skip to main content

79. Word Search

medium

Given a 2D character grid and a word, determine whether the word exists by tracing a path of adjacent cells without reusing a cell. The grid-backtracking pattern in its purest form.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an m x n grid of characters board and a string word, return true if 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.

Constraints

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consists 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

Example 2

Input
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output
true

Example 3

Input
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output
false

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Try DFS from every cell that matches word[0].

Hint 2

Carry the current character index. Match against word[index]; on match recurse into the 4 neighbors with index + 1.

Hint 3

Avoid revisiting: mark the cell visited (mutate to a sentinel like '#') before recursing, and restore after.

Hint 4

If word[index] reaches word.length, you've found it — return true.

Solution approach

Reveal approach

Try each cell as a starting point. DFS function dfs(r, c, index): if index == word.length return true (whole word matched). Out-of-bounds or mismatch -> return false. Save original char, mark board[r][c] = '#' (or use a visited set), recurse into the 4 neighbors with index + 1, OR the results, restore board[r][c]. Return whether any direction succeeded. The mark-and-restore is the backtracking step — it lets the same cell be available for other paths but blocks self-revisit within one path. Time is O(m * n * 4^L) where L is word.length; space O(L) recursion depth.

Complexity

Time
O(m * n * 4^L)
Space
O(L)

Related patterns

  • backtracking
  • dfs
  • grid-traversal

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Bloomberg
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Word Search and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →