递归专项-前缀树应用211. 添加与搜索单词 - 数据结构设计_前缀树递归添加字符串

题目：

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

实现词典类 WordDictionary ：

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

示例：

输入：
["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"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True
 

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/design-add-and-search-words-data-structure
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

之前我们的文章里面介绍了前缀树这一数据结构，本题目实际上是前缀树的一个题目的Search方面的应用，其与之前的Search的区别是多了一个万能字符.， 万能字符.可以匹配任意一个字符。所以代码稍微进行一点改动即可。核心改动逻辑如下所示：即遇到万能字符时，直接进行下一个字符的判断比较。递归方式如下：

private boolean search(Node node, String word, int index) {
            if (index >= word.length()) {
                return node.isWordTail;
            }
            char c = word.charAt(index);
            // . 代表下面的所有节点都符合要求
            if ('.' == c) {
                for (Node n : node.next.values()) {
                    if (search(n, word, index + 1)) {
                        return true;
                    }
                }
            } else if (node.next.get(word.charAt(index)) != null) {
                return search(node.next.get(word.charAt(index)), word, index + 1);
            }
            return false;
        }
    }


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

全部代码参考：

/**
 * 题目Id：211
 * 题目：添加与搜索单词 - 数据结构设计
 * 内容: //请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
 * //
 * // 实现词典类 WordDictionary ：
 * //
 * //
 * // WordDictionary() 初始化词典对象
 * // void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
 * // bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些
 * //'.' ，每个 . 都可以表示任何一个字母。
 * //
 * //
 * //
 * //
 * // 示例：
 * //
 * //
 * //输入：
 * //["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"); // return False
 * //wordDictionary.search("bad"); // return True
 * //wordDictionary.search(".ad"); // return True
 * //wordDictionary.search("b.."); // return True
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 1 <= word.length <= 500
 * // addWord 中的 word 由小写英文字母组成
 * // search 中的 word 由 '.' 或小写英文字母组成
 * // 最多调用 50000 次 addWord 和 search
 * //
 * // Related Topics 深度优先搜索 设计 字典树 字符串 
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/843621