Hard

题目描述

给定一个 m x n 二维字符网格 board 和一个单词数组 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中"相邻"单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例 1：

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

示例 2：

输入：board = [["a","b"],["c","d"]], words = ["abcb"]
输出：[]

提示：

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 12
  • board[i][j] 是小写英文字母
  • 1 <= words.length <= 3 * 10^4
  • 1 <= words[i].length <= 10
  • words[i] 由小写英文字母组成
  • words 中的所有字符串互不相同

解题思路

这是一道经典的字典树（Trie）+ DFS 回溯问题。如果对每个单词单独进行 DFS 搜索，时间复杂度会很高。

核心思路：

  1. 构建字典树（Trie）：将所有待查找的单词插入 Trie 中，这样可以在 DFS 过程中快速判断当前路径是否可能构成有效单词
  2. DFS + 回溯：从网格的每个位置开始进行深度优先搜索，利用 Trie 进行剪枝优化
  3. 剪枝策略：当当前路径不是任何单词的前缀时，立即停止搜索

优化技巧：

  • 使用 Trie 的 isWord 标记来识别完整单词
  • 在找到单词后将 isWord 设为 false，避免重复添加
  • 当 Trie 节点没有子节点且不是单词结尾时，可以删除该节点进行进一步优化
  • 使用 visited 数组标记已访问的位置，防止重复使用同一单元格

时间复杂度： O(M×N×4^L)，其中 M、N 是网格尺寸，L 是单词的最大长度。实际运行中由于 Trie 的剪枝效果，性能会显著提升。

代码实现

class Solution {
public:
    struct TrieNode {
        TrieNode* children[26];
        string word;
        
        TrieNode() {
            for (int i = 0; i < 26; i++) {
                children[i] = nullptr;
            }
            word = "";
        }
    };
    
    void buildTrie(TrieNode* root, vector<string>& words) {
        for (string& word : words) {
            TrieNode* node = root;
            for (char c : word) {
                int idx = c - 'a';
                if (!node->children[idx]) {
                    node->children[idx] = new TrieNode();
                }
                node = node->children[idx];
            }
            node->word = word;
        }
    }
    
    void dfs(vector<vector<char>>& board, int i, int j, TrieNode* node, vector<string>& result) {
        char c = board[i][j];
        if (c == '#' || !node->children[c - 'a']) return;
        
        node = node->children[c - 'a'];
        if (!node->word.empty()) {
            result.push_back(node->word);
            node->word = "";  // 避免重复
        }
        
        board[i][j] = '#';  // 标记为已访问
        
        int directions[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        for (auto& dir : directions) {
            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, node, result);
            }
        }
        
        board[i][j] = c;  // 回溯
    }
    
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        TrieNode* root = new TrieNode();
        buildTrie(root, words);
        
        vector<string> result;
        int m = board.size(), n = board[0].size();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, i, j, root, result);
            }
        }
        
        return result;
    }
};

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        class TrieNode:
            def __init__(self):
                self.children = {}
                self.word = ""
        
        def build_trie(root, words):
            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
        
        def dfs(i, j, node):
            char = board[i][j]
            if char not in node.children:
                return
            
            node = node.children[char]
            if node.word:
                result.append(node.word)
                node.word = ""  # 避免重复
            
            board[i][j] = '#'  # 标记为已访问
            
            directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
            for di, dj in directions:
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '#':
                    dfs(ni, nj, node)
            
            board[i][j] = char  # 回溯
        
        root = TrieNode()
        build_trie(root, words)
        
        result = []
        m, n = len(board), len(board[0])
        
        for i in range(m):
            for j in range(n):
                dfs(i, j, root)
        
        return result

public class Solution {
    public class TrieNode {
        public TrieNode[] Children = new TrieNode[26];
        public string Word = "";
    }
    
    private void BuildTrie(TrieNode root, string[] words) {
        foreach (string word in words) {
            TrieNode node = root;
            foreach (char c in word) {
                int idx = c - 'a';
                if (node.Children[idx] == null) {
                    node.Children[idx] = new TrieNode();
                }
                node = node.Children[idx];
            }
            node.Word = word;
        }
    }
    
    private void DFS(char[][] board, int i, int j, TrieNode node, IList<string> result) {
        char c = board[i][j];
        if (c == '#' || node.Children[c - 'a'] == null) return;
        
        node = node.Children[c - 'a'];
        if (!string.IsNullOrEmpty(node.Word)) {
            result.Add(node.Word);
            node.Word = "";  // 避免重复
        }
        
        board[i][j] = '#';  // 标记为已访问
        
        int[,] directions = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        for (int d = 0; d < 4; d++) {
            int ni = i + directions[d, 0];
            int nj = j + directions[d, 1];
            if (ni >= 0 && ni < board.Length && nj >= 0 && nj < board[0].Length) {
                DFS(board, ni, nj, node, result);
            }
        }
        
        board[i][j] = c;  // 回溯
    }
    
    public IList<string> FindWords(char[][] board, string[] words) {
        TrieNode root = new TrieNode();
        BuildTrie(root, words);
        
        IList<string> result = new List<string>();
        int m = board.Length, n = board[0].Length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                DFS(board, i, j, root, result);
            }
        }
        
        return result;
    }
}

var findWords = function(board, words) {
    class TrieNode {
        constructor() {
            this.children = {};
            this.word = "";
        }
    }
    
    function buildTrie(root, words) {
        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;
        }
    }
    
    function dfs(i, j, node) {
        let char = board[i][j];
        if (!(char in node.children)) return;
        
        node = node.children[char];
        if (node.word) {
            result.push(node.word);
            node.word = "";  // 避免重复
        }
        
        board[i][j] = '#';  // 标记为已访问
        
        let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        for (let [di, dj] of directions) {
            let ni = i + di, nj = j + dj;
            if (ni >= 0 && ni < m && nj >= 0 && nj < n && board[ni][nj] !== '#') {
                dfs(ni, nj, node);
            }
        }
        
        board[i][j] = char;  // 回溯
    }
    
    let root = new TrieNode();
    buildTrie(root, words);
    
    let result = [];
    let m = board.length, n = board[0].length;
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            dfs(i, j, root);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(M×N×4^L)，其中 M、N 是网格尺寸，L 是单词最大长度。实际运行中由于 Trie 剪枝优化，性能会显著提升
空间复杂度O(K×L)，其中 K 是单词数量，L 是单词平均长度，主要用于存储 Trie 树

相关题目