DevOps NetworkDevOpsNetwork
Join Free
Advanced

Word Search II

hardTries

Problem statement

You get a grid of lowercase letters board and a list of distinct words. A word is on the board if you can spell it by starting on some cell and repeatedly stepping to a horizontally or vertically adjacent cell, using each cell at most once within that word.

Return every word from the list that is on the board, in any order.

Searching for each word separately repeats a lot of work when words share prefixes. The interesting part is searching for all of them in one pass.

Examples

Example 1

Input: board = [["g","i","t"],["o","a","r"],["d","e","n"]], words = ["god","dear","den","rat","git"]

Output: ["dear", "den", "git", "god"]

Explanation: rat fails because a and t are only diagonal. Shown sorted; any order is accepted.

Example 2

Input: board = [["a","b"],["c","d"]], words = ["abdc","aba","acdb","ad"]

Output: ["abdc", "acdb"]

Explanation: aba would reuse the a cell, and ad needs a diagonal step.

Hints

Approach

Trie-guided backtracking. Insert every word into a trie and store the full word on the node where it ends. Then start a DFS from every cell, carrying the current trie node instead of an index:

  1. If the cell's letter has no child in the current node, stop: no word continues this way.
  2. Move to that child. If it holds a word, add it to the result and clear it so it isn't reported twice.
  3. Mark the cell used, recurse into the four neighbours, unmark it.
  4. On the way back, if the child now has no children and no word, delete it from its parent. This pruning removes finished branches so later searches skip them.

Shared prefixes are now explored once for all words that use them.

ComplexityTime O(m · n · 4 · 3^(L-1))Space O(total characters in words)
Python
def find_words(board, words):
root = {}
for w in words:
node = root
for ch in w:
node = node.setdefault(ch, {})
node["$"] = w # the word ending here
rows, cols = len(board), len(board[0])
found = []
def dfs(r, c, parent):
ch = board[r][c]
node = parent.get(ch)
if node is None:
return
word = node.pop("$", None)
if word:
found.append(word)
board[r][c] = "#"
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
dfs(nr, nc, node)
board[r][c] = ch
if not node:
del parent[ch] # prune a finished branch
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return found
print(sorted(find_words([["g", "i", "t"], ["o", "a", "r"], ["d", "e", "n"]], ["god", "dear", "den", "rat", "git"])))
print(sorted(find_words([["a", "b"], ["c", "d"]], ["abdc", "aba", "acdb", "ad"])))

Follow-up questions

  • Return where each word was found (the list of cells), not just the word.
  • What if cells may be reused within a word? (Drop the used marker; you must then bound the word length to avoid infinite loops.)

Frequently asked questions

It is the harder trie question in SWE-style loops, and it tests two things at once: backtracking on a grid, and recognising that many searches with shared prefixes should be merged into one. The same idea, matching many patterns in a single pass instead of one pass per pattern, is how multi-pattern log scanners and intrusion-detection rule engines stay fast.

The first letter can branch four ways. After that you never step back onto the cell you came from, so each later step has at most three choices. That bounds the paths per start cell, and the trie pruning usually cuts far below it.

Clearing the word stops duplicates when a word can be spelled from two places. Deleting empty nodes means later DFS calls stop as soon as they enter a region the trie no longer cares about, which matters when the board is large and most words are found early.