212. Word Search II (Hard)

Problem

Given a 2D board of characters and a list of words, return all words that can be constructed from sequentially adjacent cells. Each cell may be used at most once per word.

Example

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

LeetCode 212 · Link · Hard

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, solve Word Search for each word

Run problem 79’s single-word DFS once per word. No prefix sharing between words.

def find_words(board, words):
    rows, cols = len(board), len(board[0])

    def exist(word):
        def dfs(r, c, i):
            if i == len(word):                # L1: base case, O(1)
                return True
            if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[i]:
                return False                  # L2: bounds + match check, O(1)
            saved = board[r][c]
            board[r][c] = "#"               # L3: mark visited, O(1)
            found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1)
                     or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))  # L4: 4 directions
            board[r][c] = saved             # L5: unmark, O(1)
            return found

        for r in range(rows):               # L6: iterate over m · n cells
            for c in range(cols):
                if dfs(r, c, 0):
                    return True
        return False

    return [w for w in words if exist(w)]  # L7: run exist() W times

function findWords(board: string[][], words: string[]): string[] {
    const rows = board.length, cols = board[0].length;

    function exist(word: string): boolean {
        function dfs(r: number, c: number, i: number): boolean {
            if (i === word.length) return true;                    // L1: base case
            if (r < 0 || r >= rows || c < 0 || c >= cols
                || board[r][c] !== word[i]) return false;          // L2: bounds + match
            const saved = board[r][c];
            board[r][c] = '#';                                     // L3: mark visited
            const found = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1)
                       || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);  // L4: 4 directions
            board[r][c] = saved;                                   // L5: unmark
            return found;
        }
        for (let r = 0; r < rows; r++)                            // L6: iterate over m · n cells
            for (let c = 0; c < cols; c++)
                if (dfs(r, c, 0)) return true;
        return false;
    }

    return words.filter(w => exist(w));                            // L7: run exist() W times
}

package main

import "fmt"

func findWords(board [][]byte, words []string) []string {
    rows, cols := len(board), len(board[0])

    var exist func(word string) bool
    exist = func(word string) bool {
        var dfs func(r, c, i int) bool
        dfs = func(r, c, i int) bool {
            if i == len(word) { return true }                  // L1: base case
            if r < 0 || r >= rows || c < 0 || c >= cols ||
                board[r][c] != word[i] { return false }        // L2: bounds + match
            saved := board[r][c]
            board[r][c] = '#'                                  // L3: mark visited
            found := dfs(r+1, c, i+1) || dfs(r-1, c, i+1) ||
                dfs(r, c+1, i+1) || dfs(r, c-1, i+1)         // L4: 4 directions
            board[r][c] = saved                                // L5: unmark
            return found
        }
        for r := 0; r < rows; r++ {                           // L6: iterate over m·n cells
            for c := 0; c < cols; c++ {
                if dfs(r, c, 0) { return true }
            }
        }
        return false
    }

    var result []string
    for _, w := range words {                                  // L7: run exist() W times
        if exist(w) { result = append(result, w) }
    }
    return result
}

func runTests() {
    board1 := [][]byte{{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}}
    r1 := findWords(board1, []string{"oath","pea","eat","rain"})
    fmt.Println(r1)
}

func main() { runTests() }

final class Solution {
    func findWords(_ board: [[Character]], _ words: [String]) -> [String] {
        guard !board.isEmpty, !board[0].isEmpty else { return [] }
        return words.filter { exists($0, in: board) }
    }
    private func exists(_ word: String, in board: [[Character]]) -> Bool {
        let target = Array(word)
        var visited = Array(repeating: Array(repeating: false, count: board[0].count), count: board.count)
        func search(_ row: Int, _ column: Int, _ index: Int) -> Bool {
            guard row >= 0, row < board.count, column >= 0, column < board[0].count,
                  !visited[row][column], board[row][column] == target[index] else { return false }
            if index == target.count - 1 { return true }
            visited[row][column] = true
            defer { visited[row][column] = false }
            return search(row + 1, column, index + 1) || search(row - 1, column, index + 1)
                || search(row, column + 1, index + 1) || search(row, column - 1, index + 1)
        }
        for row in board.indices {
            for column in board[row].indices where search(row, column, 0) { return true }
        }
        return false
    }
}

Where the time goes, line by line

Variables: W = len(words), L = max word length, m = board rows, n = board columns.

Line	Per-call cost	Times executed	Contribution
L6/L7 (start cells per word)	$O(1)$	m · n per word	$O(m · n)$
L4 (4-way DFS per cell)	$O(4^L)$ worst	m · n per word	$O(m · n · 4^L)$ per word
L7 (repeat for W words)	$O(m · n · 4^L)$	W	$O(W · m · n · 4^L)$ ← dominates

Each exist(word) call launches a DFS from every cell. In the worst case, the DFS branches 4 ways at each of L levels. Multiplied by W words, shared prefix work is repeated from scratch.

Complexity

Time: $O(W · m · n · 4^L)$ , driven by L4/L7 (full DFS per word, no prefix sharing).
Space: $O(L)$ recursion.

Typically times out: overlapping prefixes across words cause massive duplicate work.

Approach 2: Insert all words into a trie, DFS the board with trie pruning

Walk the board with DFS; at each step, move down the trie along the current letter. If the letter isn’t a child of the current trie node, prune immediately. When you reach an end-of-word node, record the word.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None    # full word stored at terminal nodes (dedup helper)

def find_words(board, words):
    root = TrieNode()
    for w in words:                        # L1: build trie, O(sum of word lengths)
        node = root
        for ch in w:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.word = w

    rows, cols = len(board), len(board[0])
    found = []

    def dfs(r, c, node):
        if not (0 <= r < rows and 0 <= c < cols):
            return
        ch = board[r][c]
        if ch == "#" or ch not in node.children:  # L2: O(1) trie lookup prune
            return
        next_node = node.children[ch]
        if next_node.word:
            found.append(next_node.word)
            next_node.word = None                  # L3: O(1) dedup
        board[r][c] = "#"                          # L4: O(1) mark visited
        dfs(r + 1, c, next_node)                  # L5: 4-way DFS
        dfs(r - 1, c, next_node)
        dfs(r, c + 1, next_node)
        dfs(r, c - 1, next_node)
        board[r][c] = ch                           # L6: O(1) unmark

    for r in range(rows):                          # L7: launch from every cell
        for c in range(cols):
            dfs(r, c, root)
    return found

class TrieNode {
    children: Map<string, TrieNode> = new Map();
    word: string | null = null;
}

function findWords(board: string[][], words: string[]): string[] {
    const root = new TrieNode();
    for (const w of words) {                      // L1: build trie
        let node = root;
        for (const ch of w) {
            if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
            node = node.children.get(ch)!;
        }
        node.word = w;
    }

    const rows = board.length, cols = board[0].length;
    const found: string[] = [];

    function dfs(r: number, c: number, node: TrieNode): void {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        const ch = board[r][c];
        if (ch === '#' || !node.children.has(ch)) return;  // L2: O(1) trie lookup prune
        const nextNode = node.children.get(ch)!;
        if (nextNode.word !== null) { found.push(nextNode.word); nextNode.word = null; }  // L3: dedup
        board[r][c] = '#';                                  // L4: mark visited
        dfs(r + 1, c, nextNode); dfs(r - 1, c, nextNode);  // L5: 4-way DFS
        dfs(r, c + 1, nextNode); dfs(r, c - 1, nextNode);
        board[r][c] = ch;                                   // L6: unmark
    }

    for (let r = 0; r < rows; r++)                          // L7: launch from every cell
        for (let c = 0; c < cols; c++)
            dfs(r, c, root);
    return found;
}

package main

import "fmt"

type TrieNode struct {
    Children [26]*TrieNode
    Word     string // non-empty at terminal nodes
}

func findWords(board [][]byte, words []string) []string {
    root := &TrieNode{}
    for _, w := range words {                   // L1: build trie
        node := root
        for _, ch := range w {
            i := ch - 'a'
            if node.Children[i] == nil { node.Children[i] = &TrieNode{} }
            node = node.Children[i]
        }
        node.Word = w
    }

    rows, cols := len(board), len(board[0])
    var found []string

    var dfs func(r, c int, node *TrieNode)
    dfs = func(r, c int, node *TrieNode) {
        if r < 0 || r >= rows || c < 0 || c >= cols { return }
        ch := board[r][c]
        if ch == '#' { return }
        i := ch - 'a'
        if node.Children[i] == nil { return }  // L2: O(1) trie lookup prune
        next := node.Children[i]
        if next.Word != "" {
            found = append(found, next.Word)
            next.Word = ""                      // L3: dedup
        }
        board[r][c] = '#'                       // L4: mark visited
        dfs(r+1, c, next); dfs(r-1, c, next)   // L5: 4-way DFS
        dfs(r, c+1, next); dfs(r, c-1, next)
        board[r][c] = ch                        // L6: unmark
    }

    for r := 0; r < rows; r++ {                // L7: launch from every cell
        for c := 0; c < cols; c++ {
            dfs(r, c, root)
        }
    }
    return found
}

func runTests() {
    board1 := [][]byte{{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}}
    r1 := findWords(board1, []string{"oath","pea","eat","rain"})
    fmt.Println(r1)
}

func main() { runTests() }

final class Solution {
    func findWords(_ board: [[Character]], _ words: [String]) -> [String] {
        guard !board.isEmpty, !board[0].isEmpty else { return [] }
        let root = makeTrie(words)
        var visited = Array(repeating: Array(repeating: false, count: board[0].count), count: board.count)
        var found: Set<String> = []
        func search(_ row: Int, _ column: Int, _ node: TrieNode, _ path: String) {
            guard row >= 0, row < board.count, column >= 0, column < board[0].count, !visited[row][column],
                  let child = node.children[board[row][column]] else { return }
            let nextPath = path + String(board[row][column])
            if child.isWord { found.insert(nextPath) }
            visited[row][column] = true
            search(row + 1, column, child, nextPath); search(row - 1, column, child, nextPath)
            search(row, column + 1, child, nextPath); search(row, column - 1, child, nextPath)
            visited[row][column] = false
        }
        for row in board.indices { for column in board[row].indices { search(row, column, root, "") } }
        return words.filter { found.contains($0) }
    }
    private func makeTrie(_ words: [String]) -> TrieNode {
        let root = TrieNode()
        for word in words {
            var node = root
            for character in word {
                if node.children[character] == nil { node.children[character] = TrieNode() }
                guard let child = node.children[character] else { break }
                node = child
            }
            node.isWord = true
        }
        return root
    }
}

Where the time goes, line by line

Variables: W = len(words), L = max word length, m = board rows, n = board columns.

Line	Per-call cost	Times executed	Contribution
L1 (trie build)	$O(1)$ per char	sum of word lengths	$O(W · L)$
L2 (trie prune)	$O(1)$	each DFS step	prunes dead branches early
L7 (start cells)	$O(1)$	m · n	$O(m · n)$
L5 (4-way DFS)	$O(4^L)$ worst	m · n	$O(m · n · 4^L)$ ← dominates

The key improvement over Approach 1: all W words are searched simultaneously. When a trie path doesn’t match, the DFS prunes at L2 instead of re-launching W separate searches. Shared prefixes are explored only once.

Complexity

Time: $O(m · n · 4^L)$ , driven by L5/L7 (single DFS over all cells, guided by the trie).
Space: $O(total characters in words)$ .

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Approach 2 + dead-branch pruning

After collecting a word at a terminal node, that leaf has no remaining useful children. Delete it from its parent on the way back up the recursion. Over time the trie shrinks, cutting the DFS search space progressively.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

def find_words(board, words):
    root = TrieNode()
    for w in words:
        node = root
        for ch in w:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.word = w

    rows, cols = len(board), len(board[0])
    found = []

    def dfs(r, c, node):
        if not (0 <= r < rows and 0 <= c < cols):
            return
        ch = board[r][c]
        if ch == "#" or ch not in node.children:
            return
        next_node = node.children[ch]
        if next_node.word:
            found.append(next_node.word)
            next_node.word = None
        board[r][c] = "#"
        dfs(r + 1, c, next_node); dfs(r - 1, c, next_node)
        dfs(r, c + 1, next_node); dfs(r, c - 1, next_node)
        board[r][c] = ch
        if not next_node.children:          # L8: prune empty subtree on unwind
            del node.children[ch]           # L9: O(1) dict delete

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)
    return found

class TrieNode {
    children: Map<string, TrieNode> = new Map();
    word: string | null = null;
}

function findWords(board: string[][], words: string[]): string[] {
    const root = new TrieNode();
    for (const w of words) {
        let node = root;
        for (const ch of w) {
            if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
            node = node.children.get(ch)!;
        }
        node.word = w;
    }

    const rows = board.length, cols = board[0].length;
    const found: string[] = [];

    function dfs(r: number, c: number, node: TrieNode): void {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        const ch = board[r][c];
        if (ch === '#' || !node.children.has(ch)) return;
        const nextNode = node.children.get(ch)!;
        if (nextNode.word !== null) { found.push(nextNode.word); nextNode.word = null; }
        board[r][c] = '#';
        dfs(r + 1, c, nextNode); dfs(r - 1, c, nextNode);
        dfs(r, c + 1, nextNode); dfs(r, c - 1, nextNode);
        board[r][c] = ch;
        if (nextNode.children.size === 0 && nextNode.word === null)  // L8: prune empty subtree
            node.children.delete(ch);                                 // L9: O(1) map delete
    }

    for (let r = 0; r < rows; r++)
        for (let c = 0; c < cols; c++)
            dfs(r, c, root);
    return found;
}

package main

import "fmt"

type TrieNode struct {
    Children [26]*TrieNode
    Word     string
}

func allNil(children [26]*TrieNode) bool {
    for _, c := range children {
        if c != nil { return false }
    }
    return true
}

func findWords(board [][]byte, words []string) []string {
    root := &TrieNode{}
    for _, w := range words {
        node := root
        for _, ch := range w {
            i := ch - 'a'
            if node.Children[i] == nil { node.Children[i] = &TrieNode{} }
            node = node.Children[i]
        }
        node.Word = w
    }

    rows, cols := len(board), len(board[0])
    var found []string

    var dfs func(r, c int, node *TrieNode)
    dfs = func(r, c int, node *TrieNode) {
        if r < 0 || r >= rows || c < 0 || c >= cols { return }
        ch := board[r][c]
        if ch == '#' { return }
        i := ch - 'a'
        if node.Children[i] == nil { return }
        next := node.Children[i]
        if next.Word != "" {
            found = append(found, next.Word)
            next.Word = ""
        }
        board[r][c] = '#'
        dfs(r+1, c, next); dfs(r-1, c, next)
        dfs(r, c+1, next); dfs(r, c-1, next)
        board[r][c] = ch
        if next.Word == "" && allNil(next.Children) { // L8: prune empty subtree
            node.Children[i] = nil                    // L9: O(1) nil assignment
        }
    }

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            dfs(r, c, root)
        }
    }
    return found
}

func runTests() {
    board1 := [][]byte{{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}}
    r1 := findWords(board1, []string{"oath","pea","eat","rain"})
    fmt.Println(r1)
}

func main() { runTests() }

final class Solution {
    func findWords(_ board: [[Character]], _ words: [String]) -> [String] {
        guard !board.isEmpty, !board[0].isEmpty else { return [] }
        let root = makeTrie(words)
        var visited = Array(repeating: Array(repeating: false, count: board[0].count), count: board.count)
        var found: Set<String> = []
        func search(_ row: Int, _ column: Int, _ node: TrieNode, _ path: String) {
            guard row >= 0, row < board.count, column >= 0, column < board[0].count, !visited[row][column] else { return }
            let character = board[row][column]
            guard let child = node.children[character] else { return }
            let nextPath = path + String(character)
            if child.isWord { found.insert(nextPath); child.isWord = false }
            visited[row][column] = true
            search(row + 1, column, child, nextPath); search(row - 1, column, child, nextPath)
            search(row, column + 1, child, nextPath); search(row, column - 1, child, nextPath)
            visited[row][column] = false
            if child.children.isEmpty && !child.isWord { node.children[character] = nil }
        }
        for row in board.indices { for column in board[row].indices { search(row, column, root, "") } }
        return words.filter { found.contains($0) }
    }
    private func makeTrie(_ words: [String]) -> TrieNode {
        let root = TrieNode()
        for word in words {
            var node = root
            for character in word {
                if node.children[character] == nil { node.children[character] = TrieNode() }
                guard let child = node.children[character] else { break }
                node = child
            }
            node.isWord = true
        }
        return root
    }
}

Where the time goes, line by line

Variables: W = len(words), L = max word length, m = board rows, n = board columns.

Line	Per-call cost	Times executed	Contribution
L8 (empty check)	$O(1)$	each DFS unwind	negligible
L9 (prune leaf)	$O(1)$	≤ total trie nodes	shrinks trie over time ← key benefit

Big-O is unchanged: $O(m · n · 4^L)$ in the absolute worst case. In practice, once a word is found the trie branch leading to it is removed, so subsequent DFS calls skip that path entirely. On large word lists with many shared prefixes this gives 2-10x wall-clock speedup.

Complexity

Same $O(m · n · 4^L)$ asymptotically.
Space: $O(total chars)$ , shrinks as words are found.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space	Notes
Per-word Word Search	$O(W · m · n · 4^L)$	$O(L)$	Usually times out
Trie + board DFS	$O(m · n · 4^L)$	$O(total chars)$	Canonical
+ dead-branch pruning	same Big-O	same	Practical speedup

This problem is the canonical “why tries matter” interview question. The trie turns “run N similar searches” into “run one search against a structure that encodes all N.”

Test cases

# Quick smoke tests - paste into a REPL or save as test_212.py and run.
# Uses the canonical Approach 2 implementation (trie + board DFS).

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

def find_words(board, words):
    root = TrieNode()
    for w in words:
        node = root
        for ch in w:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.word = w

    rows, cols = len(board), len(board[0])
    found = []

    def dfs(r, c, node):
        if not (0 <= r < rows and 0 <= c < cols):
            return
        ch = board[r][c]
        if ch == "#" or ch not in node.children:
            return
        next_node = node.children[ch]
        if next_node.word:
            found.append(next_node.word)
            next_node.word = None
        board[r][c] = "#"
        dfs(r + 1, c, next_node)
        dfs(r - 1, c, next_node)
        dfs(r, c + 1, next_node)
        dfs(r, c - 1, next_node)
        board[r][c] = ch

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)
    return found

def _run_tests():
    board1 = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
    result1 = set(find_words(board1, ["oath","pea","eat","rain"]))
    assert result1 == {"oath", "eat"}

    # single cell board
    assert find_words([["a"]], ["a"]) == ["a"]
    assert find_words([["a"]], ["b"]) == []

    # word not present (requires cell reuse)
    board2 = [["a","b"],["c","d"]]
    assert set(find_words(board2, ["ab", "cd", "abdc"])) == {"ab", "cd", "abdc"}

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

class TrieNode {
    children: Map<string, TrieNode> = new Map();
    word: string | null = null;
}

function findWords(board: string[][], words: string[]): string[] {
    const root = new TrieNode();
    for (const w of words) {
        let node = root;
        for (const ch of w) {
            if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
            node = node.children.get(ch)!;
        }
        node.word = w;
    }
    const rows = board.length, cols = board[0].length;
    const found: string[] = [];
    function dfs(r: number, c: number, node: TrieNode): void {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        const ch = board[r][c];
        if (ch === '#' || !node.children.has(ch)) return;
        const nextNode = node.children.get(ch)!;
        if (nextNode.word !== null) { found.push(nextNode.word); nextNode.word = null; }
        board[r][c] = '#';
        dfs(r + 1, c, nextNode); dfs(r - 1, c, nextNode);
        dfs(r, c + 1, nextNode); dfs(r, c - 1, nextNode);
        board[r][c] = ch;
    }
    for (let r = 0; r < rows; r++)
        for (let c = 0; c < cols; c++)
            dfs(r, c, root);
    return found;
}

const board1 = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]];
const r1 = new Set(findWords(board1, ["oath","pea","eat","rain"]));
console.assert(r1.has("oath") && r1.has("eat") && r1.size === 2);
console.assert(JSON.stringify(findWords([["a"]], ["a"])) === JSON.stringify(["a"]));
console.assert(JSON.stringify(findWords([["a"]], ["b"])) === JSON.stringify([]));
const board2 = [["a","b"],["c","d"]];
const r2 = new Set(findWords(board2, ["ab","cd","abdc"]));
console.assert(r2.has("ab") && r2.has("cd") && r2.has("abdc") && r2.size === 3);
console.log("all tests pass");

package main

import (
    "fmt"
    "sort"
)

type TrieNode struct {
    Children [26]*TrieNode
    Word     string
}

func findWords(board [][]byte, words []string) []string {
    root := &TrieNode{}
    for _, w := range words {
        node := root
        for _, ch := range w {
            i := ch - 'a'
            if node.Children[i] == nil { node.Children[i] = &TrieNode{} }
            node = node.Children[i]
        }
        node.Word = w
    }
    rows, cols := len(board), len(board[0])
    var found []string
    var dfs func(r, c int, node *TrieNode)
    dfs = func(r, c int, node *TrieNode) {
        if r < 0 || r >= rows || c < 0 || c >= cols { return }
        ch := board[r][c]
        if ch == '#' { return }
        i := ch - 'a'
        if node.Children[i] == nil { return }
        next := node.Children[i]
        if next.Word != "" { found = append(found, next.Word); next.Word = "" }
        board[r][c] = '#'
        dfs(r+1, c, next); dfs(r-1, c, next)
        dfs(r, c+1, next); dfs(r, c-1, next)
        board[r][c] = ch
    }
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ { dfs(r, c, root) }
    }
    return found
}

func setsEqual(a, b []string) bool {
    if len(a) != len(b) { return false }
    sort.Strings(a); sort.Strings(b)
    for i := range a { if a[i] != b[i] { return false } }
    return true
}

func assert(condition bool, msgs ...string) {
    if !condition {
        msg := "assertion failed"
        if len(msgs) > 0 { msg = msgs[0] }
        panic(msg)
    }
}

func runTests() {
    board1 := [][]byte{{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}}
    assert(setsEqual(findWords(board1, []string{"oath","pea","eat","rain"}), []string{"eat","oath"}))
    assert(setsEqual(findWords([][]byte{{'a'}}, []string{"a"}), []string{"a"}))
    assert(setsEqual(findWords([][]byte{{'a'}}, []string{"b"}), []string{}))
    board2 := [][]byte{{'a','b'},{'c','d'}}
    assert(setsEqual(findWords(board2, []string{"ab","cd","abdc"}), []string{"ab","abdc","cd"}))
    fmt.Println("all tests pass")
}

func main() { runTests() }

Tries, dictionary representation with DFS pruning
Arrays, board with in-place visited marker

Trie Prefix Search, the prefix tree model for sharing string prefixes and pruning searches.
Backtracking, the explore, undo, and prune pattern for building candidates.

212. Word Search II (Hard)

Problem

Try it yourself

Approach 1: Brute force, solve Word Search for each word

Approach 2: Insert all words into a trie, DFS the board with trie pruning

Approach 3: Approach 2 + dead-branch pruning

Summary

Test cases

Related data structures

Related concepts