LeetCode 212. 单词搜索 II

Categories:

题目描述
思路分析
1. 解法一：Trie + DFS 回溯（推荐）
相似题目

题目描述

✅ 212. 单词搜索 II

思路分析

解法一：Trie + DFS 回溯（推荐）

核心思路：

将所有单词插入 Trie。

从每个格子出发 DFS，沿 Trie 同步向下搜索。

一旦命中单词，将其加入结果并清空 word 防止重复。

访问过的格子用临时标记，回溯时还原。

复杂度分析：

时间复杂度：O(mn · 4^L)，其中 m、n 为网格尺寸，L 为单词最大长度（剪枝后实际更小）。

空间复杂度：O(sumLen)，Trie 总长度与递归栈。

import java.util.ArrayList;
import java.util.List;

class Solution {
    private static class TrieNode {
        TrieNode[] next = new TrieNode[26];
        String word;
    }

    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = buildTrie(words);
        List<String> res = new ArrayList<>();

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

    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode node = root;
            for (int i = 0; i < w.length(); i++) {
                int idx = w.charAt(i) - 'a';
                if (node.next[idx] == null) {
                    node.next[idx] = new TrieNode();
                }
                node = node.next[idx];
            }
            node.word = w;
        }
        return root;
    }

    private void dfs(char[][] board, int x, int y, TrieNode node, List<String> res) {
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) {
            return;
        }

        char c = board[x][y];
        if (c == '#' || node.next[c - 'a'] == null) {
            return;
        }

        node = node.next[c - 'a'];
        if (node.word != null) {
            res.add(node.word);
            node.word = null;
        }

        // 标记访问
        board[x][y] = '#';
        dfs(board, x + 1, y, node, res);
        dfs(board, x - 1, y, node, res);
        dfs(board, x, y + 1, node, res);
        dfs(board, x, y - 1, node, res);
        board[x][y] = c;
    }
}

type Trie212 struct {
	children [26]*Trie212
	word     string
}

func buildTrie212(words []string) *Trie212 {
	root := &Trie212{}
	for _, w := range words {
		node := root
		for i := 0; i < len(w); i++ {
			idx := w[i] - 'a'
			if node.children[idx] == nil {
				node.children[idx] = &Trie212{}
			}
			node = node.children[idx]
		}
		node.word = w
	}
	return root
}

func findWords(board [][]byte, words []string) []string {
	root := buildTrie212(words)
	res := make([]string, 0)

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

func dfs212(board [][]byte, x int, y int, node *Trie212, res *[]string) {
	if x < 0 || x >= len(board) || y < 0 || y >= len(board[0]) {
		return
	}

	c := board[x][y]
	if c == '#' || node.children[c-'a'] == nil {
		return
	}

	node = node.children[c-'a']
	if node.word != "" {
		*res = append(*res, node.word)
		node.word = ""
	}

	board[x][y] = '#'
	dfs212(board, x+1, y, node, res)
	dfs212(board, x-1, y, node, res)
	dfs212(board, x, y+1, node, res)
	dfs212(board, x, y-1, node, res)
	board[x][y] = c
}

相似题目

题目	难度	考察点
212. 单词搜索 II	困难	Trie、DFS
79. 单词搜索	中等	DFS、回溯
208. 实现 Trie (前缀树)	中等	Trie
211. 添加与搜索单词 - 数据结构设计	中等	Trie
648. 单词替换	中等	Trie
676. 实现一个魔法字典	中等	Trie

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/38756017