LeetCode 211. 添加与搜索单词 - 数据结构设计

Categories:

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

题目描述

✅ 211. 添加与搜索单词 - 数据结构设计

思路分析

解法一：Trie + DFS（推荐）

核心思路：

使用 Trie 存储所有单词。

查询时遇到 ‘.’ 需要遍历所有子节点递归匹配。

其余字符按路径匹配。

复杂度分析：

时间复杂度：O(L * 26^k)，其中 L 为单词长度，k 为通配符数量。

空间复杂度：O(total)，用于 Trie 存储。

class WordDictionary {
    private final TrieNode root = new TrieNode();

    public WordDictionary() {
    }

    public void addWord(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.next[idx] == null) {
                node.next[idx] = new TrieNode();
            }
            node = node.next[idx];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        return dfs(word, 0, root);
    }

    private boolean dfs(String word, int pos, TrieNode node) {
        if (node == null) {
            return false;
        }
        if (pos == word.length()) {
            return node.isEnd;
        }

        char c = word.charAt(pos);
        if (c == '.') {
            for (TrieNode child : node.next) {
                if (child != null && dfs(word, pos + 1, child)) {
                    return true;
                }
            }
            return false;
        }

        return dfs(word, pos + 1, node.next[c - 'a']);
    }

    private static class TrieNode {
        TrieNode[] next = new TrieNode[26];
        boolean isEnd;
    }
}

type WordDictionary struct {
	root *TrieNode
}

type TrieNode struct {
	next  [26]*TrieNode
	isEnd bool
}

func Constructor() WordDictionary {
	return WordDictionary{root: &TrieNode{}}
}

func (w *WordDictionary) AddWord(word string) {
	node := w.root
	for i := 0; i < len(word); i++ {
		idx := word[i] - 'a'
		if node.next[idx] == nil {
			node.next[idx] = &TrieNode{}
		}
		node = node.next[idx]
	}
	node.isEnd = true
}

func (w *WordDictionary) Search(word string) bool {
	var dfs func(int, *TrieNode) bool
	dfs = func(pos int, node *TrieNode) bool {
		if node == nil {
			return false
		}
		if pos == len(word) {
			return node.isEnd
		}

		c := word[pos]
		if c == '.' {
			for i := 0; i < 26; i++ {
				if node.next[i] != nil && dfs(pos+1, node.next[i]) {
					return true
				}
			}
			return false
		}

		return dfs(pos+1, node.next[c-'a'])
	}

	return dfs(0, w.root)
}

相似题目

题目	难度	考察点
211. 添加与搜索单词 - 数据结构设计	中等	Trie
208. 实现 Trie (前缀树)	中等	Trie
212. 单词搜索 II	困难	Trie + DFS
472. 连接词	困难	Trie
1268. 搜索推荐系统	中等	Trie

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/87049048