Word Search II

Hard

The problem

Given a grid of letters and a list of words, return every word from the list that can be spelled by walking through the grid. Each step moves up, down, left or right to a touching cell, and one word cannot use the same cell twice. The result can be in any order.

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: ["oath", "eat"]
"oath" and "eat" can be traced in the grid. "pea" and "rain" cannot.
Example 2
Input: board = [["a","b"],["c","d"]], words = ["abdc","abcd"]
Output: ["abdc"]
a → b → d → c works, but b and c are diagonal, so "abcd" does not.

Limits

1 ≤ rows, columns ≤ 12
1 ≤ words.length ≤ 30,000
1 ≤ word length ≤ 10
Only lowercase letters; all words are different
If no word is found return an empty list

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Searching the grid once per word is too slow. Can one search look for all the words at the same time?

The idea

Build a trie of all words, DFS from each cell following trie edges (pruning when no child), mark visited cells, collect words at end nodes and remove found words.

Target: O(cells · 4 · 3^(L−1)) worst-case, pruned heavily by the trie

Go function shape

func findWords(board [][]byte, words []string) []string

Reference solution

Tested with go test. Try it yourself first, then compare.

// FindWords searches the board for many words at once. Insert all words into a trie, then DFS from each cell
// following trie edges: a branch with no matching child is pruned immediately. Found words are removed from
// the trie so they are reported once.
type wsNode struct {
	next map[byte]*wsNode
	word string // non-empty when a word ends here
}

func FindWords(board [][]byte, words []string) []string {
	root := &wsNode{next: map[byte]*wsNode{}}
	for _, w := range words {
		n := root
		for i := 0; i < len(w); i++ {
			if n.next[w[i]] == nil {
				n.next[w[i]] = &wsNode{next: map[byte]*wsNode{}}
			}
			n = n.next[w[i]]
		}
		n.word = w
	}
	found := []string{}
	var dfs func(r, c int, n *wsNode)
	dfs = func(r, c int, n *wsNode) {
		if r < 0 || c < 0 || r >= len(board) || c >= len(board[0]) {
			return
		}
		ch := board[r][c]
		child := n.next[ch]
		if ch == '#' || child == nil {
			return // already used on this path, or no word continues this way
		}
		if child.word != "" {
			found = append(found, child.word)
			child.word = "" // report each word once
		}
		board[r][c] = '#' // mark as used
		dfs(r+1, c, child)
		dfs(r-1, c, child)
		dfs(r, c+1, child)
		dfs(r, c-1, child)
		board[r][c] = ch // restore
	}
	for r := range board {
		for c := range board[r] {
			dfs(r, c, root)
		}
	}
	return found
}

Read the lesson: Tries