Word Search II

Problem Statement

Given an m × n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in one word.

What to notice first

• Build a Trie from all words for efficient prefix matching.
• Use DFS to explore the board and Trie simultaneously.
• Mark visited cells to avoid reusing them in one path.
• Early termination when no matching prefix exists in the Trie.

Examples

Board	Words	Output
[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]	["oath","pea","eat","rain"]	["eat","oath"]
[["a","b"],["c","d"]]	["abcb"]	[]

Constraints

• m == board.length, n == board[i].length
• 1 <= m, n <= 12
• board[i][j] is a lowercase English letter.
• 1 <= words.length <= 3 × 10^4
• 1 <= words[i].length <= 10

Real-World Applications

Where this pattern appears

• Spell checkers — find words from dictionary on a board of letters.
• Word games — validate words in Scrabble or Boggle.
• DNA sequence matching — find genetic patterns in sequences.
• Crossword puzzles — verify words on a grid.
• Text editors — multi-string find-and-replace.

Complexity Comparison

Approach	Time	Space
Recursive DFS	O(n × m × 4^l)	O(w × l)
Iterative Backtrack	O(n × m × 4^l)	O(w × l)

n,m = board dims, l = max word len, w = word count

Which approach should you learn first?

• Pick Recursive DFS for simplicity — natural for tree/graph traversal.
• Pick Iterative Backtrack if you prefer explicit state management.

Natural Fit

Recursive DFS

O(n×m×4^l) time · O(w×l) space

Explicit State

Backtrack with Visited Set

O(n×m×4^l) time · O(w×l) space

Approach 1: Recursive DFS with Trie

★ Recommended

1. Build a Trie from all words.
2. For each cell on the board, start a DFS.
3. Traverse the board following the Trie structure.
4. Mark visited cells by temporarily changing the board.
5. Restore the board during backtracking.

⏱ Time O(n×m×4^l) Board × word length 💾 Space O(w×l) Trie size

Pseudocode

function findWords(board, words):
    root = buildTrie(words)
    result = []

    for i, j in board:
        dfs(board, i, j, root, result)

    return result

function dfs(board, i, j, node, result):
    char = board[i][j]
    if char not in node.children:
        return

    nextNode = node.children[char]
    if nextNode.word exists:
        result.add(nextNode.word)
        nextNode.word = null  // Avoid duplicates

    board[i][j] = '#'  // Mark visited
    for each neighbor (ni, nj):
        dfs(board, ni, nj, nextNode, result)
    board[i][j] = char  // Restore

Solution Code

Python

word_search_ii_recursive.py

from typing import List


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


class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.word = word

        result = []
        for i in range(len(board)):
            for j in range(len(board[0])):
                self.dfs(board, i, j, root, result)
        return result

    def dfs(self, board, i, j, node, result):
        char = board[i][j]
        if char not in node.children:
            return

        next_node = node.children[char]
        if next_node.word is not None:
            result.append(next_node.word)
            next_node.word = None

        board[i][j] = '#'
        for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            ni, nj = i + di, j + dj
            if 0 <= ni < len(board) and 0 <= nj < len(board[0]):
                self.dfs(board, ni, nj, next_node, result)
        board[i][j] = char


sol = Solution()
board = [["o", "a", "a", "n"], ["e", "t", "a", "e"], ["i", "h", "k", "r"], ["i", "f", "l", "v"]]
words = ["oath", "pea", "eat", "rain"]
print(sol.findWords(board, words))  # ['eat', 'oath']

C++

word_search_ii_recursive.cpp

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>

struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    std::string word = "";
};

class Solution {
public:
    std::vector<std::string> findWords(std::vector<std::vector<char>>& board, std::vector<std::string>& words) {
        TrieNode* root = new TrieNode();
        for (const auto& word : words) {
            TrieNode* node = root;
            for (char ch : word) {
                if (node->children.find(ch) == node->children.end()) {
                    node->children[ch] = new TrieNode();
                }
                node = node->children[ch];
            }
            node->word = word;
        }

        std::vector<std::string> result;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                dfs(board, i, j, root, result);
            }
        }
        return result;
    }

private:
    void dfs(std::vector<std::vector<char>>& board, int i, int j, TrieNode* node, std::vector<std::string>& result) {
        char ch = board[i][j];
        if (node->children.find(ch) == node->children.end()) {
            return;
        }

        TrieNode* next_node = node->children[ch];
        if (!next_node->word.empty()) {
            result.push_back(next_node->word);
            next_node->word = "";
        }

        board[i][j] = '#';
        int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (auto& dir : dirs) {
            int ni = i + dir[0], nj = j + dir[1];
            if (ni >= 0 && ni < board.size() && nj >= 0 && nj < board[0].size()) {
                dfs(board, ni, nj, next_node, result);
            }
        }
        board[i][j] = ch;
    }
};

int main() {
    Solution sol;
    std::vector<std::vector<char>> board = {
        {'o', 'a', 'a', 'n'},
        {'e', 't', 'a', 'e'},
        {'i', 'h', 'k', 'r'},
        {'i', 'f', 'l', 'v'}
    };
    std::vector<std::string> words = {"oath", "pea", "eat", "rain"};
    auto result = sol.findWords(board, words);
    for (const auto& word : result) {
        std::cout << word << " ";
    }
    std::cout << std::endl;
    return 0;
}

Java

WordSearchII_Recursive.java

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    String word = null;
}

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                node.children.putIfAbsent(c, new TrieNode());
                node = node.children.get(c);
            }
            node.word = word;
        }

        List<String> result = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root, result);
            }
        }
        return result;
    }

    private void dfs(char[][] board, int i, int j, TrieNode node, List<String> result) {
        char ch = board[i][j];
        if (!node.children.containsKey(ch)) {
            return;
        }

        TrieNode next = node.children.get(ch);
        if (next.word != null) {
            result.add(next.word);
            next.word = null;
        }

        board[i][j] = '#';
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int[] dir : dirs) {
            int ni = i + dir[0], nj = j + dir[1];
            if (ni >= 0 && ni < board.length && nj >= 0 && nj < board[0].length) {
                dfs(board, ni, nj, next, result);
            }
        }
        board[i][j] = ch;
    }
}

public class WordSearchII_Recursive {
    public static void main(String[] args) {
        Solution sol = new Solution();
        char[][] board = {
            {'o', 'a', 'a', 'n'},
            {'e', 't', 'a', 'e'},
            {'i', 'h', 'k', 'r'},
            {'i', 'f', 'l', 'v'}
        };
        String[] words = {"oath", "pea", "eat", "rain"};
        System.out.println(sol.findWords(board, words));
    }
}

JavaScript

word_search_ii_recursive.js

class TrieNode {
    constructor() {
        this.children = {};
        this.word = null;
    }
}

class Solution {
    findWords(board, words) {
        const root = new TrieNode();
        for (let word of words) {
            let node = root;
            for (let char of word) {
                if (!(char in node.children)) {
                    node.children[char] = new TrieNode();
                }
                node = node.children[char];
            }
            node.word = word;
        }

        const result = [];
        for (let i = 0; i < board.length; i++) {
            for (let j = 0; j < board[0].length; j++) {
                this.dfs(board, i, j, root, result);
            }
        }
        return result;
    }

    dfs(board, i, j, node, result) {
        const char = board[i][j];
        if (!(char in node.children)) {
            return;
        }

        const nextNode = node.children[char];
        if (nextNode.word !== null) {
            result.push(nextNode.word);
            nextNode.word = null;
        }

        board[i][j] = '#';
        const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
        for (let [di, dj] of dirs) {
            const ni = i + di, nj = j + dj;
            if (ni >= 0 && ni < board.length && nj >= 0 && nj < board[0].length) {
                this.dfs(board, ni, nj, nextNode, result);
            }
        }
        board[i][j] = char;
    }
}

const sol = new Solution();
const board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]];
const words = ["oath","pea","eat","rain"];
console.log(sol.findWords(board, words));

Rust

word_search_ii_recursive.rs

use std::collections::HashMap;
use std::rc::Rc;
use std::cell::RefCell;

#[derive(Default)]
struct TrieNode {
    children: HashMap<char, Rc<RefCell<TrieNode>>>,
    word: Option<String>,
}

struct Solution;

impl Solution {
    pub fn find_words(board: &mut Vec<Vec<char>>, words: Vec<String>) -> Vec<String> {
        let root = Rc::new(RefCell::new(TrieNode::default()));

        for word in words {
            let mut node = Rc::clone(&root);
            for ch in word.chars() {
                let mut node_ref = node.borrow_mut();
                node = Rc::clone(
                    node_ref
                        .children
                        .entry(ch)
                        .or_insert_with(|| Rc::new(RefCell::new(TrieNode::default()))),
                );
            }
            node.borrow_mut().word = Some(word);
        }

        let mut result = Vec::new();
        for i in 0..board.len() {
            for j in 0..board[0].len() {
                Solution::dfs(board, i, j, Rc::clone(&root), &mut result);
            }
        }
        result
    }

    fn dfs(
        board: &mut Vec<Vec<char>>,
        i: usize,
        j: usize,
        node: Rc<RefCell<TrieNode>>,
        result: &mut Vec<String>,
    ) {
        let ch = board[i][j];
        let mut node_ref = node.borrow_mut();

        if !node_ref.children.contains_key(&ch) {
            return;
        }

        let next_node = Rc::clone(node_ref.children.get(&ch).unwrap());
        drop(node_ref);

        let mut next_ref = next_node.borrow_mut();
        if let Some(word) = next_ref.word.take() {
            result.push(word);
        }
        drop(next_ref);

        board[i][j] = '#';
        let dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)];
        for (di, dj) in &dirs {
            let ni = (i as i32 + di) as usize;
            let nj = (j as i32 + dj) as usize;
            if ni < board.len() && nj < board[0].len() {
                Solution::dfs(board, ni, nj, Rc::clone(&next_node), result);
            }
        }
        board[i][j] = ch;
    }
}

fn main() {
    let mut board = vec![
        vec!['o', 'a', 'a', 'n'],
        vec!['e', 't', 'a', 'e'],
        vec!['i', 'h', 'k', 'r'],
        vec!['i', 'f', 'l', 'v'],
    ];
    let words = vec!["oath".to_string(), "pea".to_string(), "eat".to_string(), "rain".to_string()];
    let result = Solution::find_words(&mut board, words);
    println!("{:?}", result);
}

Go

word_search_ii_recursive.go

package main

import "fmt"

type TrieNode struct {
  children map[rune]*TrieNode
  word     string
}

func findWords(board [][]byte, words []string) []string {
  root := &TrieNode{children: make(map[rune]*TrieNode)}
  for _, word := range words {
    node := root
    for _, ch := range word {
      if _, exists := node.children[ch]; !exists {
        node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
      }
      node = node.children[ch]
    }
    node.word = word
  }

  result := []string{}
  for i := 0; i < len(board); i++ {
    for j := 0; j < len(board[0]); j++ {
      dfs(board, i, j, root, &result)
    }
  }
  return result
}

func dfs(board [][]byte, i, j int, node *TrieNode, result *[]string) {
  ch := rune(board[i][j])
  if _, exists := node.children[ch]; !exists {
    return
  }

  nextNode := node.children[ch]
  if nextNode.word != "" {
    *result = append(*result, nextNode.word)
    nextNode.word = ""
  }

  board[i][j] = '#'
  dirs := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
  for _, dir := range dirs {
    ni, nj := i+dir[0], j+dir[1]
    if ni >= 0 && ni < len(board) && nj >= 0 && nj < len(board[0]) {
      dfs(board, ni, nj, nextNode, result)
    }
  }
  board[i][j] = byte(ch)
}

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

Approach 2: Backtracking with Visited Set

🎯 Interview Favourite

Instead of modifying the board, track visited cells in a separate set. Useful when board is read-only.

⏱ Time O(n×m×4^l) Board exploration 💾 Space O(n×m+w×l) Visited set + Trie

Solution Code

Python

word_search_ii_backtrack.py

from typing import List


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


class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.word = word

        self.result = []
        visited = set()

        def backtrack(i, j, node):
            if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
                return
            if (i, j) in visited:
                return

            char = board[i][j]
            if char not in node.children:
                return

            visited.add((i, j))
            next_node = node.children[char]

            if next_node.word is not None:
                self.result.append(next_node.word)
                next_node.word = None

            for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                backtrack(i + di, j + dj, next_node)

            visited.remove((i, j))

        for i in range(len(board)):
            for j in range(len(board[0])):
                backtrack(i, j, root)

        return self.result


sol = Solution()
board = [["o", "a", "a", "n"], ["e", "t", "a", "e"], ["i", "h", "k", "r"], ["i", "f", "l", "v"]]
words = ["oath", "pea", "eat", "rain"]
print(sol.findWords(board, words))  # ['eat', 'oath']

C++

word_search_ii_backtrack.cpp

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>

struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    std::string word = "";
};

class Solution {
private:
    std::vector<std::string> result;
    std::unordered_set<std::pair<int, int>, std::hash<std::pair<int, int>>> visited;

    void backtrack(std::vector<std::vector<char>>& board, int i, int j, TrieNode* node) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) {
            return;
        }

        char ch = board[i][j];
        if (node->children.find(ch) == node->children.end()) {
            return;
        }

        TrieNode* next_node = node->children[ch];
        if (!next_node->word.empty()) {
            result.push_back(next_node->word);
            next_node->word = "";
        }

        board[i][j] = '#';
        int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (auto& dir : dirs) {
            backtrack(board, i + dir[0], j + dir[1], next_node);
        }
        board[i][j] = ch;
    }

public:
    std::vector<std::string> findWords(std::vector<std::vector<char>>& board, std::vector<std::string>& words) {
        TrieNode* root = new TrieNode();
        for (const auto& word : words) {
            TrieNode* node = root;
            for (char ch : word) {
                if (node->children.find(ch) == node->children.end()) {
                    node->children[ch] = new TrieNode();
                }
                node = node->children[ch];
            }
            node->word = word;
        }

        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                backtrack(board, i, j, root);
            }
        }
        return result;
    }
};

int main() {
    Solution sol;
    std::vector<std::vector<char>> board = {
        {'o', 'a', 'a', 'n'},
        {'e', 't', 'a', 'e'},
        {'i', 'h', 'k', 'r'},
        {'i', 'f', 'l', 'v'}
    };
    std::vector<std::string> words = {"oath", "pea", "eat", "rain"};
    auto result = sol.findWords(board, words);
    for (const auto& word : result) {
        std::cout << word << " ";
    }
    std::cout << std::endl;
    return 0;
}

Java

WordSearchII_Backtrack.java

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    String word = null;
}

class Solution {
    private List<String> result = new ArrayList<>();

    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                node.children.putIfAbsent(c, new TrieNode());
                node = node.children.get(c);
            }
            node.word = word;
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                backtrack(board, i, j, root);
            }
        }
        return result;
    }

    private void backtrack(char[][] board, int i, int j, TrieNode node) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return;
        }

        char ch = board[i][j];
        if (!node.children.containsKey(ch)) {
            return;
        }

        TrieNode next = node.children.get(ch);
        if (next.word != null) {
            result.add(next.word);
            next.word = null;
        }

        board[i][j] = '#';
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int[] dir : dirs) {
            backtrack(board, i + dir[0], j + dir[1], next);
        }
        board[i][j] = ch;
    }
}

public class WordSearchII_Backtrack {
    public static void main(String[] args) {
        Solution sol = new Solution();
        char[][] board = {
            {'o', 'a', 'a', 'n'},
            {'e', 't', 'a', 'e'},
            {'i', 'h', 'k', 'r'},
            {'i', 'f', 'l', 'v'}
        };
        String[] words = {"oath", "pea", "eat", "rain"};
        System.out.println(sol.findWords(board, words));
    }
}

JavaScript

word_search_ii_backtrack.js

class TrieNode {
    constructor() {
        this.children = {};
        this.word = null;
    }
}

class Solution {
    findWords(board, words) {
        const root = new TrieNode();
        for (let word of words) {
            let node = root;
            for (let char of word) {
                if (!(char in node.children)) {
                    node.children[char] = new TrieNode();
                }
                node = node.children[char];
            }
            node.word = word;
        }

        const result = [];

        const backtrack = (i, j, node) => {
            if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
                return;
            }

            const char = board[i][j];
            if (!(char in node.children)) {
                return;
            }

            const nextNode = node.children[char];
            if (nextNode.word !== null) {
                result.push(nextNode.word);
                nextNode.word = null;
            }

            board[i][j] = '#';
            backtrack(i + 1, j, nextNode);
            backtrack(i - 1, j, nextNode);
            backtrack(i, j + 1, nextNode);
            backtrack(i, j - 1, nextNode);
            board[i][j] = char;
        };

        for (let i = 0; i < board.length; i++) {
            for (let j = 0; j < board[0].length; j++) {
                backtrack(i, j, root);
            }
        }

        return result;
    }
}

const sol = new Solution();
const board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]];
const words = ["oath","pea","eat","rain"];
console.log(sol.findWords(board, words));

Rust

word_search_ii_backtrack.rs

use std::collections::HashMap;
use std::rc::Rc;
use std::cell::RefCell;

#[derive(Default)]
struct TrieNode {
    children: HashMap<char, Rc<RefCell<TrieNode>>>,
    word: Option<String>,
}

struct Solution;

impl Solution {
    pub fn find_words(board: &mut Vec<Vec<char>>, words: Vec<String>) -> Vec<String> {
        let root = Rc::new(RefCell::new(TrieNode::default()));

        for word in words {
            let mut node = Rc::clone(&root);
            for ch in word.chars() {
                let mut node_ref = node.borrow_mut();
                node = Rc::clone(
                    node_ref
                        .children
                        .entry(ch)
                        .or_insert_with(|| Rc::new(RefCell::new(TrieNode::default()))),
                );
            }
            node.borrow_mut().word = Some(word);
        }

        let result = std::cell::RefCell::new(Vec::new());
        for i in 0..board.len() {
            for j in 0..board[0].len() {
                Solution::backtrack(board, i, j, Rc::clone(&root), &result);
            }
        }
        result.into_inner()
    }

    fn backtrack(
        board: &mut Vec<Vec<char>>,
        i: usize,
        j: usize,
        node: Rc<RefCell<TrieNode>>,
        result: &std::cell::RefCell<Vec<String>>,
    ) {
        let ch = board[i][j];
        let mut node_ref = node.borrow_mut();

        if !node_ref.children.contains_key(&ch) {
            return;
        }

        let next_node = Rc::clone(node_ref.children.get(&ch).unwrap());
        drop(node_ref);

        let mut next_ref = next_node.borrow_mut();
        if let Some(word) = next_ref.word.take() {
            result.borrow_mut().push(word);
        }
        drop(next_ref);

        board[i][j] = '#';
        let dirs = [(0, 1), (1, 0), (0_usize.wrapping_sub(1)), (0, 0_usize.wrapping_sub(1))];

        if i + 1 < board.len() {
            Solution::backtrack(board, i + 1, j, Rc::clone(&next_node), result);
        }
        if i > 0 {
            Solution::backtrack(board, i - 1, j, Rc::clone(&next_node), result);
        }
        if j + 1 < board[0].len() {
            Solution::backtrack(board, i, j + 1, Rc::clone(&next_node), result);
        }
        if j > 0 {
            Solution::backtrack(board, i, j - 1, Rc::clone(&next_node), result);
        }

        board[i][j] = ch;
    }
}

fn main() {
    let mut board = vec![
        vec!['o', 'a', 'a', 'n'],
        vec!['e', 't', 'a', 'e'],
        vec!['i', 'h', 'k', 'r'],
        vec!['i', 'f', 'l', 'v'],
    ];
    let words = vec!["oath".to_string(), "pea".to_string(), "eat".to_string(), "rain".to_string()];
    let result = Solution::find_words(&mut board, words);
    println!("{:?}", result);
}

Go

word_search_ii_backtrack.go

package main

import "fmt"

type TrieNode struct {
  children map[rune]*TrieNode
  word     string
}

func findWords(board [][]byte, words []string) []string {
  root := &TrieNode{children: make(map[rune]*TrieNode)}
  for _, word := range words {
    node := root
    for _, ch := range word {
      if _, exists := node.children[ch]; !exists {
        node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
      }
      node = node.children[ch]
    }
    node.word = word
  }

  result := []string{}

  var backtrack func(int, int, *TrieNode)
  backtrack = func(i, j int, node *TrieNode) {
    if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) {
      return
    }

    ch := rune(board[i][j])
    if _, exists := node.children[ch]; !exists {
      return
    }

    nextNode := node.children[ch]
    if nextNode.word != "" {
      result = append(result, nextNode.word)
      nextNode.word = ""
    }

    board[i][j] = '#'
    backtrack(i+1, j, nextNode)
    backtrack(i-1, j, nextNode)
    backtrack(i, j+1, nextNode)
    backtrack(i, j-1, nextNode)
    board[i][j] = byte(ch)
  }

  for i := 0; i < len(board); i++ {
    for j := 0; j < len(board[0]); j++ {
      backtrack(i, j, root)
    }
  }

  return result
}

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

Common mistakes

Watch for these pitfalls

• Forgetting to restore the board during backtracking (DFS approach).
• Reusing a cell multiple times in one word.
• Not checking if the character exists in the Trie before recursing.
• Adding duplicate words to the result (set word = null after adding).
• Not handling boundary checks before recursing.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

word_search_ii_space_optimized.py

"""
Solution for Word Search II
"""

def solve():
    """Implementation for approach 3 of Word Search II"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

word_search_ii_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Word Search II
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

WordSearchIiSpaceOptimized.java

/**
 * Solution for Word Search II
 * Approach 3
 */
public class WordSearchIiSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

word_search_ii_space_optimized.js

/**
 * Solution for Word Search II
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

word_search_ii_space_optimized.rs

/// Solution for Word Search II
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

word_search_ii_space_optimized.go

package main

import "fmt"

// Solution for Word Search II
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Implement Trie (Prefix Tree) ↗ Medium #208
• Design Add and Search Words Data Structure ↗ Medium #211
• Word Search ↗ Medium #79

Interview Tips

Key trade-offs to discuss

• Trie vs. HashSet: Trie enables early termination when prefix doesn’t match; HashSet requires checking all words.
• Board modification: Modifying the board saves space but violates immutability; use visited set if needed.
• Optimization: Prune the Trie after each word is found to reduce search space.
• Follow-up: How would you handle a very large word list? (Stream processing, lazy Trie building.)
• Edge cases: Board with one cell, single-letter words, words not on board, overlapping words.

← Previous
#211 Design Add and Search Words Next
#213 House Robber II →