LeetCode LCR 064. 实现一个魔法字典

Categories:

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

题目描述

✅ LCR 064. 实现一个魔法字典

思路分析

解法一：Trie + 一次替换 DFS（推荐）

核心思路：

将字典构建成 Trie，查询时在 Trie 上 DFS。

允许且仅允许一次字符替换，递归参数记录已替换次数。

当走到单词末尾时，只有 isEnd 且替换次数为 1 才为匹配。

复杂度分析：

时间复杂度：O(26 * L)，其中 L 表示单词长度，最多尝试 26 个分支。

空间复杂度：O(total)，Trie 存储所有词典字符。

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

    private final TrieNode root = new TrieNode();

    public MagicDictionary() {}

    public void buildDict(String[] dictionary) {
        for (String word : dictionary) {
            insert(word);
        }
    }

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

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

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

        int cur = word.charAt(idx) - 'a';
        for (int i = 0; i < 26; i++) {
            if (node.next[i] == null) {
                continue;
            }
            int nextDiff = diff + (i == cur ? 0 : 1);
            if (nextDiff > 1) {
                continue;
            }
            if (dfs(word, idx + 1, nextDiff, node.next[i])) {
                return true;
            }
        }
        return false;
    }
}

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

type MagicDictionary struct {
    root *TrieNode
}

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

func (m *MagicDictionary) BuildDict(dictionary []string) {
    for _, word := range dictionary {
        m.insert(word)
    }
}

func (m *MagicDictionary) Search(searchWord string) bool {
    return dfsMagic(searchWord, 0, 0, m.root)
}

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

func dfsMagic(word string, idx int, diff int, node *TrieNode) bool {
    if node == nil {
        return false
    }
    if idx == len(word) {
        return node.isEnd && diff == 1
    }

    cur := word[idx] - 'a'
    for i := 0; i < 26; i++ {
        if node.next[i] == nil {
            continue
        }
        nextDiff := diff
        if byte(i) != cur {
            nextDiff++
        }
        if nextDiff > 1 {
            continue
        }
        if dfsMagic(word, idx+1, nextDiff, node.next[i]) {
            return true
        }
    }
    return false
}

相似题目

题目	难度	考察点
208. 实现 Trie (前缀树)	中等	Trie
211. 添加与搜索单词 - 数据结构设计	中等	DFS
648. 单词替换	中等	前缀树
720. 词典中最长的单词	中等	Trie
1032. 字符流	困难	Trie

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/59912056