0348HardArrayStringBacktrackingTrieMatrix

Letter Plate Catalogue

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

An engraved plate holds one lowercase letter per cell: board[r][c] is the letter in row r, column c. You are also handed a catalogue of distinct words.

A word is traceable when you can put a stylus on some cell and then move it one cell at a time, up, down, left or right, so that the letters visited spell the word from start to finish. While tracing a single word the stylus may never revisit a cell it has already used. Each word is traced from scratch, so a cell used while tracing one word is free again for the next one.

Return every word of the catalogue that is traceable on this plate. The returned words may be in any order, and each traceable word appears once.

Examples

Example 1

Input: board = [["s","e","a"],["t","x","r"],["o","p","t"]], words = ["sea","set","sto","art","top","extra"]
Output: ["sea","sto","art","top"]

`sea` runs across the top row. `sto` runs down the first column. `art` runs down the last column. `top` starts at the `t` in the middle of the left column, drops to `o`, then steps right to `p`. `set` cannot be traced because no `t` touches the `e`, and `extra` runs out of neighbours after `ext`.

Example 2

Input: board = [["a","b"],["a","a"]], words = ["aab","aba","bb"]
Output: ["aab","aba"]

`aab` starts at the bottom-left `a`, steps up to the top-left `a`, then right to `b`. `aba` starts at the top-left `a`, steps right to `b`, then down to the bottom-right `a`. The plate holds a single `b`, so `bb` has nowhere to go after its first letter.

Example 3

Input: board = [["s","s"],["s","s"]], words = ["ss","sss","ssss","sssss"]
Output: ["ss","sss","ssss"]

The plate holds four cells of `s`, so a stylus can spell two, three or four of them by snaking through distinct cells. `sssss` would need a fifth cell, and no cell may be reused inside one word.

Constraints

m == board.length
n == board[r].length
1 <= m, n <= 12
board[r][c] is a lowercase English letter.
1 <= words.length <= 3 * 10^4
1 <= words[i].length <= 10
words[i] is made of lowercase English letters.
The words of the catalogue are pairwise distinct.

The values you return may be in any order.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

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

Java

public List<String> findWords(char[][] board, String[] words)

The intended approach

Time O(total catalogue length + m * n * 4^L), L the longest wordSpace O(total catalogue length) for the prefix tree, plus O(L) for the walk

Insert the catalogue into a prefix tree, then start one backtracking walk from every cell and carry a tree node alongside the stylus. A walk stops as soon as the letter under the stylus is not a child of the current node, which keeps the search from exploring paths no word can use. Cells are marked while the stylus stands on them and unmarked on the way out. A word is removed from the tree when it is first traced, and a node with no children left is deleted from its parent.

Pythonentry point: find_words

def find_words(board, words):
    # Load the catalogue into a prefix tree so one walk of the plate can chase every
    # candidate at once, and a walk stops the moment the letters under it stop being
    # a prefix of anything.  A word is lifted out of the tree when it is traced, so
    # it can never be reported twice, and exhausted branches are pruned away.
    # Time O(sum of word lengths + m * n * 4^L) in the worst case, where L is the
    # longest word.  Space O(sum of word lengths) for the tree plus the trace path.
    root = {}
    for w in words:
        node = root
        for ch in w:
            node = node.setdefault(ch, {})
        node["#"] = w
    rows = len(board)
    cols = len(board[0])
    found = []

    def trace(r, c, node):
        letter = board[r][c]
        step = node.get(letter)
        if step is None:
            return
        word = step.pop("#", None)
        if word is not None:
            found.append(word)
        board[r][c] = "*"
        if r > 0 and board[r - 1][c] != "*":
            trace(r - 1, c, step)
        if r + 1 < rows and board[r + 1][c] != "*":
            trace(r + 1, c, step)
        if c > 0 and board[r][c - 1] != "*":
            trace(r, c - 1, step)
        if c + 1 < cols and board[r][c + 1] != "*":
            trace(r, c + 1, step)
        board[r][c] = letter
        if not step:
            del node[letter]

    for r in range(rows):
        for c in range(cols):
            trace(r, c, root)
    return found

The obvious version

Handle one word at a time with its own search: push every cell carrying the first letter, then pop partial traces off a stack and extend them with neighbours that carry the next letter and are not already in that trace's used set.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_traceable_words(board, words):
    rows = len(board)
    cols = len(board[0])

    def can_trace(word):
        stack = []
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == word[0]:
                    stack.append((r, c, 1, frozenset([(r, c)])))
        while stack:
            r, c, k, used = stack.pop()
            if k == len(word):
                return True
            need = word[k]
            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nr = r + dr
                nc = c + dc
                if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in used:
                    if board[nr][nc] == need:
                        stack.append((nr, nc, k + 1, used | {(nr, nc)}))
        return False

    out = []
    for w in words:
        if can_trace(w):
            out.append(w)
    return out

How this problem was checked

Reference solution executed against 7 test cases — 7 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in