添加与搜索单词

七崽爱吃小饼干2026/01/14阅读 0专栏算法合集

请你设计一个数据结构，支持添加新单词和查找字符串是否与任何先前添加的字符串匹配。

实现词典类 WordDictionary ：

WordDictionary() 初始化词典对象
void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。

示例：

codeType

输入：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：
[null,null,null,null,false,true,true,true]

解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // 返回 False
wordDictionary.search("bad"); // 返回 True
wordDictionary.search(".ad"); // 返回 True
wordDictionary.search("b.."); // 返回 True

提示：

1 <= word.length <= 25
addWord 中的 word 由小写英文字母组成
search 中的 word 由 '.' 或小写英文字母组成
最多调用 104 次 addWord 和 search

解法

和一般的Trie不同，这里还需要有能力查找带通配符的字符串。这个也比较好处理，碰到通配符的时候，只需要逐个对孩子进行深度搜索即可。

class TrieNode {
    children: (TrieNode | 0)[];
    isEnd: boolean;

    constructor() {
        this.children = new Array(26).fill(0);
        this.isEnd = false;
    }

    insert(word: string): void {
        let node: TrieNode = this;
        for (let i = 0; i < word.length; i++) {
            const ch = word[i];
            const index = ch.charCodeAt(0) - 'a'.charCodeAt(0);
            if (node.children[index] === 0) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index] as TrieNode;
        }
        node.isEnd = true;
    }

    getChildren(): (TrieNode | 0)[] {
        return this.children;
    }

    isWordEnd(): boolean {
        return this.isEnd;
    }
}

class WordDictionary {
    trieRoot: TrieNode;

    constructor() {
        this.trieRoot = new TrieNode();
    }

    addWord(word: string): void {
        this.trieRoot.insert(word);
    }

    search(word: string): boolean {
        const dfs = (index: number, node: TrieNode): boolean => {
            if (index === word.length) {
                return node.isEnd;
            }
            const ch = word[index];
            if (ch !== '.') {
                const idx = ch.charCodeAt(0) - 'a'.charCodeAt(0);
                const child = node.children[idx];
                if (child && dfs(index + 1, child as TrieNode)) {
                    return true;
                }
            } else { // 如果是通配符，就逐个从孩子中进行深度遍历匹配
                for (const child of node.children) {
                    if (child && dfs(index + 1, child as TrieNode)) {
                        return true;
                    }
                }
            }
            return false;
        };
        return dfs(0, this.trieRoot);
    }
}