0212. 单词搜索 II【困难】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 字典树 + 回溯

1. 📝 题目描述

• leetcode

给定一个 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 中的所有字符串互不相同

2. 🎯 s.1 - 字典树 + 回溯

c

typedef struct TrieNode {
    struct TrieNode* children[26];
    char* word;
} TrieNode;

TrieNode* createNode() {
    return (TrieNode*)calloc(1, sizeof(TrieNode));
}

void insertWord(TrieNode* root, char* word) {
    TrieNode* node = root;
    for (int i = 0; word[i]; i++) {
        int idx = word[i] - 'a';
        if (!node->children[idx]) node->children[idx] = createNode();
        node = node->children[idx];
    }
    node->word = word;
}

void dfs(char** board, int m, int n, int i, int j, TrieNode* node, char** res, int* resSize) {
    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == '#') return;
    int idx = board[i][j] - 'a';
    if (!node->children[idx]) return;
    node = node->children[idx];
    if (node->word) {
        res[(*resSize)++] = node->word;
        node->word = NULL;
    }
    char tmp = board[i][j];
    board[i][j] = '#';
    dfs(board, m, n, i + 1, j, node, res, resSize);
    dfs(board, m, n, i - 1, j, node, res, resSize);
    dfs(board, m, n, i, j + 1, node, res, resSize);
    dfs(board, m, n, i, j - 1, node, res, resSize);
    board[i][j] = tmp;
}

char** findWords(char** board, int boardSize, int* boardColSize, char** words, int wordsSize, int* returnSize) {
    TrieNode* root = createNode();
    for (int i = 0; i < wordsSize; i++) insertWord(root, words[i]);
    char** res = (char**)malloc(sizeof(char*) * wordsSize);
    *returnSize = 0;
    int m = boardSize, n = boardColSize[0];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            dfs(board, m, n, i, j, root, res, returnSize);
    return res;
}

js

/**
 * @param {character[][]} board
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function (board, words) {
  const root = {}
  // 构建字典树
  for (const word of words) {
    let node = root
    for (const ch of word) {
      if (!node[ch]) node[ch] = {}
      node = node[ch]
    }
    node.word = word
  }
  const m = board.length,
    n = board[0].length
  const res = []
  function dfs(i, j, node) {
    if (i < 0 || i >= m || j < 0 || j >= n) return
    const ch = board[i][j]
    if (ch === '#' || !node[ch]) return
    node = node[ch]
    if (node.word) {
      res.push(node.word)
      node.word = null // 去重
    }
    board[i][j] = '#'
    dfs(i + 1, j, node)
    dfs(i - 1, j, node)
    dfs(i, j + 1, node)
    dfs(i, j - 1, node)
    board[i][j] = ch
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      dfs(i, j, root)
    }
  }
  return res
}

py

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = {}
        for word in words:
            node = root
            for ch in word:
                node = node.setdefault(ch, {})
            node['#'] = word

        m, n = len(board), len(board[0])
        res = []

        def dfs(i, j, node):
            if i < 0 or i >= m or j < 0 or j >= n:
                return
            ch = board[i][j]
            if ch not in node:
                return
            node = node[ch]
            if '#' in node:
                res.append(node.pop('#'))
            board[i][j] = '.'
            dfs(i + 1, j, node)
            dfs(i - 1, j, node)
            dfs(i, j + 1, node)
            dfs(i, j - 1, node)
            board[i][j] = ch

        for i in range(m):
            for j in range(n):
                dfs(i, j, root)
        return res

• 时间复杂度：$O(m\times n\times 4^L)$，其中 $m\times n$ 是网格大小，$L$ 是单词最大长度
• 空间复杂度：$O(T)$，其中 $T$ 是所有单词的字符总数

算法思路：

• 将所有单词插入字典树，然后从网格每个位置出发 DFS
• 沿着字典树节点探索，节点不存在则剪枝，找到单词后置空以去重