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

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

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

实现词典类 WordDictionary ：

• WordDictionary() 初始化词典对象

• void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配

• bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 '.' ，每个 '.' 都可以表示任何一个字母。

• 示例 1：

输入：
["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 由 '.' 或小写英文字母组成
最多调用 10^4 次 addWord 和 search

思路

可以使用 Trie（前缀树） 数据结构。Trie 非常适合处理字符串匹配问题，特别是在添加和查询操作频繁的情况下。

由于查询的字符串 word 中可能包含通配符 .，我们需要在 search 方法中进行特殊处理。. 可以匹配任何一个字母，因此在搜索时，遇到 . 时，需要递归地尝试匹配所有可能的子节点。

1. TrieNode 定义：每个 TrieNode 代表一个节点，它有一个固定大小的数组 children 来存储26个字母（a-z）的后续节点。此外，节点还需要一个布尔值 isEnd 来标记当前节点是否为某个完整单词的结束。
2. addDFS 方法：从根节点开始插入字符串的每个字符，如果节点不存在则创建新的节点。
3. searchDFS 方法：这是递归搜索的核心函数。根据字符的情况（普通字符或 .），选择不同的搜索策略。普通字符按照字符索引匹配，. 则尝试当前节点的所有子节点。

• 时间复杂度:O(m)，其中 m 是插入单词的平均长度。
• 空间复杂度:O(mn)，其中 m 是插入单词的平均长度, n 是插入单词的数量。

代码

class WordDictionary {
    private static class TrieNode {
        TrieNode[] children;
        boolean isEnd;

        public TrieNode() {
            // 每个节点有26个字母分支
            this.children = new TrieNode[26];
            // 是否是某个单词的结束
            this.isEnd = false;
        }
    }

    private TrieNode root;

    // 初始化数据结构对象
    public WordDictionary() {
        root = new TrieNode();
    }

    // 向前缀树中插入字符串 word
    public void addWord(String word) {
        addDFS(root, word, 0);
    }

    // 查找字符串是否与任何添加的字符串匹配
    public boolean search(String word) {
        return searchDFS(root, word, 0);
    }

    private void addDFS(TrieNode node, String word, int index) {
        if (word.length() == index) {
            return;
        }
        char c = word.charAt(index);
        if (node.children[c - 'a'] == null) {
            // 创建新的节点
            node.children[c - 'a'] = new TrieNode();
        }
        node = node.children[c - 'a'];
        if (word.length() - 1 == index) {
            // 插入完毕，标记为单词的结束
            node.isEnd = true;
        }
        addDFS(node, word, index + 1);
    }

    private boolean searchDFS(TrieNode node, String word, int index) {
        // 当遍历到字符串末尾时，检查是否是单词结束
        if (word.length() == index) {
            return node.isEnd;
        }
        char c = word.charAt(index);
        // 如果当前字符是 '.'，则需要尝试所有的子节点
        if (c == '.') {
            for (int i = 0; i < 26; i++) {
                // 只要有一个匹配成功就返回true
                if (node.children[i] != null && searchDFS(node.children[i], word, index + 1)) {
                    return true;
                }
            }
            // 如果所有子节点都没有匹配成功，返回false
            return false;
        } else {
            if (node.children[c - 'a'] == null) {
                // 如果路径中某个节点不存在，则返回 false
                return false;
            }
            node = node.children[c - 'a'];
            // 如果找到了对应的单词且是单词的结束，返回 true
            if (index == word.length() - 1 && node.isEnd) {
                return true;
            }
            return searchDFS(node, word, index + 1);
        }
    }
}