Quick Overview

A grid search coding question: decide whether a word can be traced through a letter grid by moving between horizontally or vertically adjacent cells without reusing any cell. It tests backtracking search, bookkeeping of visited cells and pruning under small grid and word-length bounds.

Search for a Word Along Adjacent Cells of a Letter Grid Without Reusing Cells

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a grid of letters and a word, decide whether the word can be spelled by a path through the grid. The path starts at any cell and moves at each step to a horizontally or vertically adjacent cell, and it may use each cell at most once. The letters of the cells along the path, in order, must equal the word. ### Function Signature ```python def word_exists(board: list[list[str]], word: str) -> bool: ``` ### Rules - Two cells are adjacent when they share an edge: up, down, left or right. Diagonal moves are not allowed. - A cell may appear at most once in a path, even if its letter is needed again later in the word. - Matching is case-sensitive. - Return `True` if at least one such path exists, otherwise `False`. ### Constraints - `1 <= rows <= 6` and `1 <= cols <= 6`, and every row has the same length. - `1 <= len(word) <= 15` - Every cell holds exactly one English letter, uppercase or lowercase, and `word` consists of English letters only. ### Examples All three examples use this board; positions are `(row, column)`, counted from 0. ```text board = [["C", "A", "T"], ["X", "R", "S"], ["B", "O", "D"]] ``` **Example 1** ```text Input: board as above, word = "CATS" Output: True ``` The path `(0,0) C`, `(0,1) A`, `(0,2) T`, `(1,2) S` spells the word. **Example 2** ```text Input: board as above, word = "TSDOR" Output: True ``` The path `(0,2) T`, `(1,2) S`, `(2,2) D`, `(2,1) O`, `(1,1) R` spells the word. **Example 3** ```text Input: board as above, word = "ARA" Output: False ``` The only `A` is at `(0,1)`. After moving to the `R` at `(1,1)`, the only adjacent `A` is the cell already used, so the word cannot be completed.

Overview: A grid search coding question: decide whether a word can be traced through a letter grid by moving between horizontally or vertically adjacent cells without reusing any cell. It tests backtracking search, bookkeeping of visited cells and pruning under small grid and word-length bounds.

Given a rectangular grid of letters `board` and a string `word`, decide whether `word` can be spelled by a path through the grid. Implement `word_exists(board, word)`. A path starts at any cell and, at each step, moves to a cell that is horizontally or vertically adjacent to the current one. The letters of the cells along the path, read in order, must equal `word`. **Rules** - Two cells are adjacent when they share an edge: up, down, left or right. Diagonal moves are not allowed. - A cell may appear at most once in a path, even if its letter is needed again later in the word. - Matching is case-sensitive: `"a"` and `"A"` are different letters. - Return `True` if at least one such path exists, otherwise `False` (`true` / `false` in JavaScript, Java and C++). Each cell of `board` is a string holding exactly one letter. Positions are written `(row, column)`, counted from 0. **Example 1** ```text board = [["C", "A", "T"], ["X", "R", "S"], ["B", "O", "D"]] word = "CATS" Output: True ``` The path `(0,0) C`, `(0,1) A`, `(0,2) T`, `(1,2) S` spells the word. **Example 2** ```text board = the same board as Example 1 word = "ARA" Output: False ``` The only `A` is at `(0,1)`. After moving to the `R` at `(1,1)`, the only adjacent `A` is the cell already used, so the word cannot be completed. **Constraints** - `1 <= rows <= 6` and `1 <= cols <= 6`, and every row has the same length. - `1 <= len(word) <= 15` - Every cell holds exactly one English letter, uppercase or lowercase, and `word` consists of English letters only.

Constraints

  • 1 <= rows <= 6 and 1 <= cols <= 6, and every row has the same length.
  • 1 <= len(word) <= 15
  • Every cell holds exactly one English letter, uppercase or lowercase, and word consists of English letters only.

Examples

Input: ([['C', 'A', 'T'], ['X', 'R', 'S'], ['B', 'O', 'D']], 'CATS')

Expected Output: True

Explanation: Source example 1: (0,0) C, (0,1) A, (0,2) T, (1,2) S spells the word.

Input: ([['C', 'A', 'T'], ['X', 'R', 'S'], ['B', 'O', 'D']], 'TSDOR')

Expected Output: True

Explanation: Source example 2: turning path (0,2) T, (1,2) S, (2,2) D, (2,1) O, (1,1) R.

Hints

  1. From any cell, the next letter can only come from one of the at most four cells that share an edge with it; diagonal cells never count as next to each other.
  2. A letter that occurs twice in the word needs two different cells holding that letter, as the ARA example shows.
  3. Letters are compared exactly as written, so a lowercase cell never matches an uppercase letter in the word.

Trace a Word Through a Letter Grid

mediumBloombergSoftware Engineer

Given a rectangular grid of letters board and a string word, decide whether word can be spelled by a path through the grid. Implement word_exists(board, word).

A path starts at any cell and, at each step, moves to a cell that is horizontally or vertically adjacent to the current one. The letters of the cells along the path, read in order, must equal word.

Rules

  • Two cells are adjacent when they share an edge: up, down, left or right. Diagonal moves are not allowed.
  • A cell may appear at most once in a path, even if its letter is needed again later in the word.
  • Matching is case-sensitive: "a" and "A" are different letters.
  • Return True if at least one such path exists, otherwise False (true / false in JavaScript, Java and C++).

Each cell of board is a string holding exactly one letter. Positions are written (row, column), counted from 0.

Example 1

board = [["C", "A", "T"],
         ["X", "R", "S"],
         ["B", "O", "D"]]
word  = "CATS"
Output: True

The path (0,0) C, (0,1) A, (0,2) T, (1,2) S spells the word.

Example 2

board = the same board as Example 1
word  = "ARA"
Output: False

The only A is at (0,1). After moving to the R at (1,1), the only adjacent A is the cell already used, so the word cannot be completed.

Constraints

  • 1 <= rows <= 6 and 1 <= cols <= 6, and every row has the same length.
  • 1 <= len(word) <= 15
  • Every cell holds exactly one English letter, uppercase or lowercase, and word consists of English letters only.

Examples

Example 1
Input
([['C', 'A', 'T'], ['X', 'R', 'S'], ['B', 'O', 'D']], 'CATS')
Output
True
Notes
Source example 1: (0,0) C, (0,1) A, (0,2) T, (1,2) S spells the word.
Example 2
Input
([['C', 'A', 'T'], ['X', 'R', 'S'], ['B', 'O', 'D']], 'TSDOR')
Output
True
Notes
Source example 2: turning path (0,2) T, (1,2) S, (2,2) D, (2,1) O, (1,1) R.

Constraints

  • •1 <= rows <= 6 and 1 <= cols <= 6, and every row has the same length.
  • •1 <= len(word) <= 15
  • •Every cell holds exactly one English letter, uppercase or lowercase, and word consists of English letters only.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def word_exists(board: list[list[str]], word: str) -> bool:
Sample call
word_exists([['C', 'A', 'T'], ['X', 'R', 'S'], ['B', 'O', 'D']], 'CATS')
Language
Case 1
Input
([['C', 'A', 'T'], ['X', 'R', 'S'], ['B', 'O', 'D']], 'CATS')
Expected
True
Case 2
Input
([['C', 'A', 'T'], ['X', 'R', 'S'], ['B', 'O', 'D']], 'TSDOR')
Expected
True

Browse More Questions

Show the approach

Approach

Approach: letter-count pruning followed by depth-first backtracking from an anchor letter.

  1. Count how many cells hold each letter. If the word needs some letter more times than the board holds it (this also covers a word longer than the number of cells), no path can exist, so return False.
  2. Choose an anchor: the first position p in the word whose letter is rarest on the board. Every valid path contains a cell for word[p]; from that cell the path continues forward through word[p+1], ..., word[L-1] and backward through word[p-1], ..., word[0]. The search therefore places the sequence word[p:] followed by reversed word[:p], starting only from cells that hold the rare letter.
  3. Each step places one letter. While the forward part is being placed, the next cell must be edge-adjacent to the last placed cell. When the forward part is complete, the next cell must be adjacent to the anchor cell; after that it must be adjacent to the last placed cell again. A boolean grid marks the cells on the current partial path: a cell is marked when placed and unmarked when the search backs out of it, so no path uses a cell twice while abandoned attempts free their cells for later attempts.

Invariant: the marked cells are exactly the distinct cells of the current partial path, and consecutive letters of the word sit on edge-adjacent cells.

Correctness: every valid path c0, ..., c(L-1) corresponds to exactly one placement order c_p, ..., c_(L-1), c_(p-1), ..., c_0, and the search tries every in-bounds, unmarked, letter-matching neighbour at each step, so it finds that order. Conversely, a complete placement is a set of distinct cells whose consecutive word letters are edge-adjacent, i.e. a valid path. So the function returns True exactly when a path exists.

Edge cases: a 1x1 board; single-row and single-column boards; a word longer than the number of cells; letters that differ only in case (compared exactly); diagonal neighbours (never considered); a repeated letter that needs two different cells.

Time complexity:
O(R * C * 3^L), where R x C is the board size and L = len(word); the letter counting adds O(R * C + L)
Space complexity:
O(R * C + L)