Word Search II

Hard· trie· backtracking

Problem

Given a grid of letters and a list of words, return every word that can be traced in the grid. A word is formed by moving between horizontally or vertically adjacent cells, never reusing a cell within the same word.

Examples

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]

Output: ["oath","eat"]

Input: board = [["a","b"],["c","d"]], words = ["abcb"]

Output: []

Constraints

• 1 <= rows, cols <= 12
• 1 <= words.length <= 3 * 10^4
• 1 <= words[i].length <= 10, all words unique

Hints & approach

Hint 1

Running a separate grid search for every word repeats the same exploration many times.

Hint 2

Build a trie of all the words, then do one DFS per cell guided by the trie.

Hint 3

Stop exploring as soon as the current path is not a prefix of any word, and prune trie nodes once their words are found.

Approachtry the hints first

Insert every word into a trie, storing the full word at its terminal node. From each cell, DFS while simultaneously stepping down the trie: if the cell's letter has no child in the current node, prune immediately. When you reach a node holding a word, add it to the result and clear it so it is not reported twice. Mark cells as visited during the DFS and restore them on return. Removing leaf nodes once they are exhausted keeps later searches from walking dead branches.

Time O(R * C * 4 * 3^(L-1)), L = max word length · Space O(total characters in words)

← PreviousDesign Add and Search Words Data Structure DoneBack to Tries