Word Search II - LeetCodee

Problem Description

Given an m x 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 a word.

Examples

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"]

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

Jump to Solution: Python Java C++ JavaScript C#

Python Solution


class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.word = ''

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # Build Trie
        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.is_end = True
            node.word = word
        
        rows, cols = len(board), len(board[0])
        result = set()
        
        def dfs(row: int, col: int, node: TrieNode) -> None:
            # Check boundaries and if character exists in trie
            if (row < 0 or row >= rows or col < 0 or col >= cols or
                board[row][col] not in node.children):
                return
            
            char = board[row][col]
            next_node = node.children[char]
            
            # Found a word
            if next_node.is_end:
                result.add(next_node.word)
            
            # Mark as visited
            board[row][col] = '#'
            
            # Check all 4 directions
            for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                dfs(row + dx, col + dy, next_node)
            
            # Restore the cell
            board[row][col] = char
        
        # Start DFS from each cell
        for i in range(rows):
            for j in range(cols):
                dfs(i, j, root)
        
        return list(result)

Java Solution


class TrieNode {
    Map children = new HashMap<>();
    boolean isEnd = false;
    String word = "";
}

class Solution {
    public List findWords(char[][] board, String[] words) {
        // Build Trie
        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.isEnd = true;
            node.word = word;
        }
        
        Set result = new HashSet<>();
        int rows = board.length, cols = board[0].length;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                dfs(board, i, j, root, result);
            }
        }
        
        return new ArrayList<>(result);
    }
    
    private void dfs(char[][] board, int row, int col, TrieNode node, Set result) {
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length ||
            !node.children.containsKey(board[row][col])) {
            return;
        }
        
        char char = board[row][col];
        TrieNode nextNode = node.children.get(char);
        
        if (nextNode.isEnd) {
            result.add(nextNode.word);
        }
        
        board[row][col] = '#';
        
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int[] dir : dirs) {
            dfs(board, row + dir[0], col + dir[1], nextNode, result);
        }
        
        board[row][col] = char;
    }
}

C++ Solution


class TrieNode {
public:
    unordered_map children;
    bool isEnd;
    string word;
    
    TrieNode() {
        isEnd = false;
    }
    
    ~TrieNode() {
        for (auto& pair : children) {
            delete pair.second;
        }
    }
};

class Solution {
public:
    vector findWords(vector>& board, vector& words) {
        // Build Trie
        TrieNode* root = new TrieNode();
        for (const string& word : words) {
            TrieNode* node = root;
            for (char c : word) {
                if (!node->children[c]) {
                    node->children[c] = new TrieNode();
                }
                node = node->children[c];
            }
            node->isEnd = true;
            node->word = word;
        }
        
        unordered_set result;
        int rows = board.size(), cols = board[0].size();
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                dfs(board, i, j, root, result);
            }
        }
        
        delete root;
        return vector(result.begin(), result.end());
    }
    
private:
    void dfs(vector>& board, int row, int col, TrieNode* node,
             unordered_set& result) {
        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size() ||
            !node->children.count(board[row][col])) {
            return;
        }
        
        char char = board[row][col];
        TrieNode* nextNode = node->children[char];
        
        if (nextNode->isEnd) {
            result.insert(nextNode->word);
        }
        
        board[row][col] = '#';
        
        vector> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (const auto& dir : dirs) {
            dfs(board, row + dir.first, col + dir.second, nextNode, result);
        }
        
        board[row][col] = char;
    }
};

JavaScript Solution


class TrieNode {
    constructor() {
        this.children = new Map();
        this.isEnd = false;
        this.word = '';
    }
}

/**
 * @param {character[][]} board
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function(board, words) {
    // Build Trie
    const root = new TrieNode();
    for (const word of words) {
        let node = root;
        for (const char of word) {
            if (!node.children.has(char)) {
                node.children.set(char, new TrieNode());
            }
            node = node.children.get(char);
        }
        node.isEnd = true;
        node.word = word;
    }
    
    const result = new Set();
    const rows = board.length;
    const cols = board[0].length;
    
    const dfs = (row, col, node) => {
        if (row < 0 || row >= rows || col < 0 || col >= cols ||
            !node.children.has(board[row][col])) {
            return;
        }
        
        const char = board[row][col];
        const nextNode = node.children.get(char);
        
        if (nextNode.isEnd) {
            result.add(nextNode.word);
        }
        
        board[row][col] = '#';
        
        const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
        for (const [dx, dy] of dirs) {
            dfs(row + dx, col + dy, nextNode);
        }
        
        board[row][col] = char;
    };
    
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            dfs(i, j, root);
        }
    }
    
    return Array.from(result);
};

C# Solution


public class TrieNode {
    public Dictionary children = new Dictionary();
    public bool isEnd = false;
    public string word = "";
}

public class Solution {
    public IList FindWords(char[][] board, string[] words) {
        // Build Trie
        var root = new TrieNode();
        foreach (var word in words) {
            var node = root;
            foreach (var c in word) {
                if (!node.children.ContainsKey(c)) {
                    node.children[c] = new TrieNode();
                }
                node = node.children[c];
            }
            node.isEnd = true;
            node.word = word;
        }
        
        var result = new HashSet();
        int rows = board.Length, cols = board[0].Length;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                DFS(board, i, j, root, result);
            }
        }
        
        return result.ToList();
    }
    
    private void DFS(char[][] board, int row, int col, TrieNode node, HashSet result) {
        if (row < 0 || row >= board.Length || col < 0 || col >= board[0].Length ||
            !node.children.ContainsKey(board[row][col])) {
            return;
        }
        
        char char = board[row][col];
        var nextNode = node.children[char];
        
        if (nextNode.isEnd) {
            result.Add(nextNode.word);
        }
        
        board[row][col] = '#';
        
        var dirs = new[] { new[] {0, 1}, new[] {1, 0}, new[] {0, -1}, new[] {-1, 0} };
        foreach (var dir in dirs) {
            DFS(board, row + dir[0], col + dir[1], nextNode, result);
        }
        
        board[row][col] = char;
    }
}

Complexity Analysis

Time Complexity: O(M × N × 4^L) where:
- M × N is the size of the board
- L is the maximum length of words
- 4 is the number of possible directions
Space Complexity: O(K) where K is the total number of characters in all words (for the Trie)

Solution Explanation

This solution combines Trie and DFS:

Trie Construction:
- Build Trie from words
- Store complete words at leaf nodes
- Optimize search process
Board Search:
- DFS from each cell
- Match characters with Trie
- Track visited cells

Key Points

Trie optimization
DFS implementation
Visited cell marking
Result collection

Optimization Tips

Early termination
Memory management
Path pruning
Word storage

Edge Cases

Empty board
Empty words list
No matches
Single cell board