Tries Prefix trees

426. Word Search II

You are given a grid of lowercase letters, board, as a list of strings, one per row, and a list of different words, words. Return every word from words that a path through the grid spells.

A path starts at any cell and moves one step at a time to the cell directly above, below, left or right of the current one. Diagonal steps are not allowed. The letters along the path, in order, must spell the word, and one path cannot use the same cell twice. Different words may use the same cells.

Return each word at most once, even if several paths spell it. The words can come back in any order, and any order is accepted. The examples list them alphabetically.

Example 1

Input: board = ["stop", "ears", "rlan"] words = ["star", "step", "seat", "real", "plan"]

Output: ["real","seat","star"]

Explanation: "star" goes along the top row from s to t, then down to a and right to r. "seat" and "real" also have paths. "step" fails because no e is next to the t, and "plan" fails because the p has no l next to it.

Example 2

Input: board = ["aa", "ab"] words = ["aaa", "aaab", "aaaa", "ba"]

Output: ["aaa","aaab","ba"]

Explanation: "aaab" goes from the bottom-left a up, right, and down to the b. "aaaa" needs four a's, and the board has only three.

Example 3

Input: board = ["q"], words = ["qq", "x"]

Output: []

Explanation: "qq" would use the only cell twice, and the board has no x. No word is found, so the answer is an empty list.

Check your understanding

Work out the answer for this input before you write any code.

board = ["cat"], words = ["cat", "tac", "act", "at"]

Constraints

1 ≤ board.length ≤ 12
1 ≤ board[i].length ≤ 12, and every row has the same length
1 ≤ words.length ≤ 3 · 10⁴
1 ≤ words[i].length ≤ 10
board and every words[i] hold only lowercase English letters.
All the words in words are different.

Clarifying questions

What you would ask an interviewer before writing any code.