Show problems as
Classic problem #212HardArrayStringBacktrackingTrieMatrix

Word Search II

Real-world version: Letter Plate Catalogue
Tracked in this browser only
Read Word Search II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstRecursive Search · Recursion, animated step by step

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_words(board: list[list[str]], words: list[str]) -> list[str]:
Java
public List<String> findWords(char[][] board, String[] words)

More on the same topics