Katkat
Back

Find Which Words From a List Can Be Traced Through Adjacent Cells of a Letter Grid

GleanSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Given a letter grid and a list of words, return every word that can be spelled by a path of edge-adjacent cells without reusing a cell, sorted lexicographically. Covers the single-word search and its many-words follow-up, and tests backtracking and pruning on a large word list.

You are given an m x n grid of lowercase letters and a list of words. A word can be traced in the grid if there is a sequence of cells whose letters spell the word in order, where each cell is horizontally or vertically adjacent to the previous one and no cell is used twice within that word.

Return every word from the list that can be traced in the grid.

The interview started with the single-word version (decide whether one given word can be traced), and the follow-up asked for a whole list of words at once. A list containing one word is the single-word version.

Function Signature

def find_words(board: list[list[str]], words: list[str]) -> list[str]:

Rules

  • Adjacent means sharing an edge: up, down, left or right. Diagonal cells are not adjacent.
  • A cell may appear at most once in the path of one word. Different words may reuse the same cells.
  • A word that appears more than once in words appears at most once in the output.
  • Return the traceable words sorted in ascending lexicographic order, or an empty list if none can be traced.

Constraints

  • 1 <= m, n <= 12, where m = len(board) and n = len(board[i]) for every row i
  • Every board[i][j] is a single lowercase English letter.
  • 1 <= len(words) <= 30000
  • 1 <= len(words[i]) <= 10, and every word consists of lowercase English letters.

Examples

Example 1

Input: board = [
 ["c", "a", "t"],
 ["r", "o", "s"],
 ["e", "d", "g"]
]
words = ["cat", "cot", "rod", "red", "dog", "oat"]
Output: ["cat", "oat", "red", "rod"]

"cot" fails because c at (0, 0) and o at (1, 1) are only diagonal neighbours. "dog" fails because the g at (2, 2) is not adjacent to the only o, at (1, 1).

Example 2

Input: board = [
 ["a", "b"],
 ["c", "d"]
]
words = ["abdc", "aba", "abcd", "a", "a"]
Output: ["a", "abdc"]

"aba" would need the single a cell twice. "abcd" needs b at (0, 1) followed by c at (1, 0), which are diagonal. "a" is listed twice but returned once.

Example 3

Input: board = [["a", "a"]]
words = ["aaa"]
Output: []

The grid has only two a cells, and a cell cannot be reused within one word.