211. 添加与搜索单词 - 数据结构设计
211. 添加与搜索单词 - 数据结构设计
🟠 🔖 深度优先搜索
设计
字典树
字符串
🔗 力扣
LeetCode
题目
Design a data structure that supports adding new words and finding if a string matches any previously added string.
Implement the WordDictionary
class:
WordDictionary()
Initializes the object.void addWord(word)
Addsword
to the data structure, it can be matched later.bool search(word)
Returnstrue
if there is any string in the data structure that matchesword
orfalse
otherwise.word
may contain dots'.'
where dots can be matched with any letter.
Example:
Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]
Explanation
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
Constraints:
1 <= word.length <= 25
word
inaddWord
consists of lowercase English letters.word
insearch
consist of'.'
or lowercase English letters.- There will be at most
2
dots inword
forsearch
queries. - At most
10^4
calls will be made toaddWord
andsearch
.
题目大意
请你设计一个数据结构,支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 WordDictionary
:
WordDictionary()
初始化词典对象void addWord(word)
将word
添加到数据结构中,之后可以对它进行匹配bool search(word)
如果数据结构中存在字符串与word
匹配,则返回true
;否则,返回false
。word 中可能包含一些 '.' ,每个 . 都可以表示任何一个字母。
解题思路
关键点是,搜索可以包含正则表达式中的 .
,代表任意一个字符。因此,通常的字符串匹配方式无法直接适用,应该用 字典树(Trie) 来设计。
- 字典树 (Trie):这是一个经典的数据结构,适合用于存储和检索字符串。字典树的每个节点代表一个字符,并且具有一个标记,用来判断是否到达一个完整的单词。
- 递归搜索:在搜索时,如果遇到普通字符,沿着 Trie 进行普通的搜索;如果遇到
.
,则需要递归地搜索当前节点的所有子节点,直到找到匹配的字符或最终没有匹配。
addWord
:O(m)
,其中m
是插入单词的长度。search
:最坏情况下O(n)
,n
是字典树中所有节点的总数,因为.
可能会触发对所有路径的遍历。
代码
var WordDictionary = function () {
this.root = {}; // 初始化字典树的根节点
};
// 添加单词到字典树
/**
* @param {string} word
* @return {void}
*/
WordDictionary.prototype.addWord = function (word) {
let node = this.root;
for (let char of word) {
// 如果当前字符不存在,则创建一个新节点
if (!node[char]) {
node[char] = {};
}
node = node[char]; // 移动到下一个节点
}
node.isEnd = true; // 单词结束标记
};
// 搜索单词,支持 . 通配符
/**
* @param {string} word
* @return {boolean}
*/
WordDictionary.prototype.search = function (word) {
// 定义一个递归搜索函数
const dfs = (node, i) => {
// 如果到达了单词末尾,检查是否是一个完整的单词
if (i == word.length) {
return node.isEnd == true;
}
const char = word[i];
// 如果遇到 .,递归地搜索所有子节点
if (char === '.') {
for (let key in node) {
if (key !== 'isEnd' && dfs(node[key], i + 1)) {
return true;
}
}
return false;
} else {
// 如果是普通字符,沿着字典树继续搜索
// 如果路径不存在,返回 false
if (!node[char]) {
return false;
}
// 否则,继续搜索下一个字符
return dfs(node[char], i + 1);
}
};
// 从根节点开始搜索
return dfs(this.root, 0);
};
/**
* Your WordDictionary object will be instantiated and called as such:
* var obj = new WordDictionary()
* obj.addWord(word)
* var param_2 = obj.search(word)
*/
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
208 | 实现 Trie (前缀树) | [✓] | 设计 字典树 哈希表 1+ | |
745 | 前缀和后缀搜索 | 设计 字典树 数组 2+ | ||
2301 | 替换字符后匹配 | 数组 哈希表 字符串 1+ | ||
2416 | 字符串的前缀分数和 | [✓] | 字典树 数组 字符串 1+ | |
3042 | 统计前后缀下标对 I | 字典树 数组 字符串 3+ | ||
3045 | 统计前后缀下标对 II | 字典树 数组 字符串 3+ |