LESSON 505 OF 671 · TRIES

Word Search II

Practice O(R · C · 4^L)

Given a grid of letters board with R rows and C columns, and an array of strings words, return every word of words that can be traced on the board.

A word is traced by a path of cells: its first letter is in some cell, and each next letter is in a cell next to the previous one, horizontally or vertically (not diagonally). A cell can be used only once in the same word.

Return each word found once, in any order: the output lists the words in alphabetical order. If no word can be traced, the answer is empty.

Example 1:

Input: board = [
  ["o", "a", "a", "n"],
  ["e", "t", "a", "e"],
  ["i", "h", "k", "r"],
  ["i", "f", "l", "v"]
], words = ["oath", "pea", "eat", "rain"]
Output: ["eat", "oath"]
Explanation: "oath" starts at the top-left "o", goes right to "a", down to "t" and down again to "h".
"eat" starts at the "e" at the right end of the second row, then goes left to "a" and left again to "t".
The board has no "p", so "pea" can't be traced, and no "a" is next to the "r", so neither can "rain".

Example 2:

Input: board = [
  ["a", "b"],
  ["c", "d"]
], words = ["abdb", "ad"]
Output: []
Explanation: "abdb" would go a → b → d and then back to "b", but that cell is already used in this word.
"a" and "d" touch only at a corner, so "ad" can't be traced either.

Example 3:

Input: board = [
  ["s", "e", "e"],
  ["n", "e", "t"]
], words = ["see", "seen", "set", "net", "tee", "teen"]
Output: ["net", "see", "seen", "tee"]
Explanation: "see" can be traced in two ways (its last "e" is either to the right or below), but it is listed once.
"seen" goes s → e → e (the one below) → n, so the path of "see" is the start of the path of "seen".
"set" can't be traced: the only "e" next to "s" is not next to "t". Neither can "teen": in every path t → e → e, the second "e" is the top middle one, which is not next to "n".

Constraints:

1 <= R, C <= 12
Every cell of board holds a lowercase English letter.
1 <= words.length <= 3 * 10⁴
1 <= words[i].length <= 10
words[i] consists of lowercase English letters, and all the words are different.

Note:

Searching the board once for every word repeats the same work for words that start the same way. Put the words in a trie instead, and search the board once: a depth-first search from each cell follows only the trie's paths. With words of at most L letters, each search goes at most L cells deep, so the time is O(R * C * 4^L), plus the time to build the trie, whatever the number of words.

STEP 1 OF 25

Guided

Ctrl + Enter to check