帮企业建设网站销售,网站架构分析工具,做网站的集团,云南省做网站开发的公司排名文章目录 添加与搜索单词 - 数据结构设计思路一思路二 添加与搜索单词 - 数据结构设计 请你设计一个数据结构#xff0c;支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。 实现词典类 WordDictionary #xff1a; ● WordDictionary() 初始化词典对象 ● voi… 文章目录 添加与搜索单词 - 数据结构设计思路一思路二 添加与搜索单词 - 数据结构设计 请你设计一个数据结构支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。 实现词典类 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); // 返回 False
wordDictionary.search(bad); // 返回 True
wordDictionary.search(.ad); // 返回 True
wordDictionary.search(b..); // 返回 True思路一
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.isWord true;
};/** * param {string} word* return {boolean}*/
WordDictionary.prototype.search function(word) {return this.dfs(this.root, word, 0);
};WordDictionary.prototype.dfs function(node, word, index) {const char word[index];if (index word.length) {return node.isWord true;}if (char ! .) {if (node[char] this.dfs(node[char], word, index 1)) {return true;}} else {for (let childChar in node) {if (childChar ! isWord this.dfs(node[childChar], word, index 1)) {return true;}}}return false;
};讲解 WordDictionary 构造函数 初始化 Trie 结构WordDictionary构造函数初始化一个空的字典树根节点是一个空对象{}用于后续插入和搜索操作。 addWord 方法 遍历单词遍历给定的单词word的每一个字符char从根节点开始。插入字符到 Trie对于每一个字符如果当前节点没有对应的子节点则创建一个新的子节点。然后将当前节点更新为这个子节点继续处理下一个字符。标记单词结束当所有字符都处理完毕后将最后一个节点的isWord属性设为true表示一个单词的结束。 search 方法 调用 DFS 方法search方法接收一个可能包含通配符.的单词然后调用dfs方法从根节点开始进行深度优先搜索。处理字符对于每个字符如果字符不是通配符.则检查当前节点是否有对应的子节点如果有则递归调用dfs继续搜索如果没有则返回false。处理通配符如果遇到通配符.则遍历当前节点的所有子节点递归调用dfs方法进行搜索如果在任一子节点的搜索中返回true则立即返回true。 dfs 方法 结束条件如果当前索引index等于输入单词的长度说明已经遍历完所有字符此时如果当前节点的isWord属性为true则返回true表示找到匹配的单词。非通配符处理如果当前字符不是通配符.检查当前节点是否有对应的子节点如果有则递归调用dfs方法继续搜索否则返回false。通配符处理如果当前字符是通配符.遍历当前节点的所有子节点除了isWord属性对每个子节点递归调用dfs方法进行搜索如果在任一子节点的搜索中返回true则立即返回true。 思路二
class TrieNode {constructor() {this.children {};this.isEndOfWord false;}
}class WordDictionary {constructor() {this.root new TrieNode();}// 添加单词addWord(word) {let node this.root;for (let char of word) {if (!node.children[char]) {node.children[char] new TrieNode();}node node.children[char];}node.isEndOfWord true; // 标记单词的结束}// 搜索单词search(word) {return this._searchInNode(word, this.root);}// 递归搜索函数_searchInNode(word, node) {for (let i 0; i word.length; i) {const char word[i];if (char .) {// 如果是 ., 遍历所有子节点for (let child in node.children) {if (this._searchInNode(word.slice(i 1), node.children[child])) {return true;}}return false; // 如果没有匹配的子节点} else {// 如果不是 ., 直接查找子节点if (!node.children[char]) {return false; // 如果没有这个字符返回 false}node node.children[char];}}return node.isEndOfWord; // 返回是否是一个完整单词}
}讲解 TrieNode 类 children一个对象用于存储当前节点的所有子节点。每个子节点的键是字符值是对应的 TrieNode 实例。isEndOfWord一个布尔值标记当前节点是否是一个完整单词的结束。若为 true则表示从根节点到该节点的路径形成了一个完整的单词。 WordDictionary 类 constructor()初始化 WordDictionary 类时创建一个根节点 this.root所有单词都将从这个节点开始构建。 addWord() 方法 这个方法用于将一个新单词添加到字典中。从根节点开始遍历单词的每个字符。如果当前字符的子节点不存在则创建一个新的 TrieNode。移动到当前字符的子节点继续处理下一个字符。最后将最后一个节点的 isEndOfWord 属性设置为 true表示这个节点是一个完整单词的结束。 search() 方法 这个方法用于查找字典中是否存在与给定字符串匹配的单词。它调用 _searchInNode 方法来执行实际的搜索操作。 _searchInNode() 递归搜索 这个方法是递归的核心部分负责在 Trie 中查找与给定字符串匹配的单词。遍历 word 的每个字符。如果字符是 “ . ”则需要检查当前节点的所有子节点 对每个子节点递归调用 _searchInNode 方法传入剩余的字符串从 i 1 开始。如果在任何一个子节点中找到了匹配返回 true。如果所有子节点都没有找到匹配返回 false。 如果字符不是 “ . ”则直接查找当前字符对应的子节点 如果子节点不存在返回 false。如果子节点存在移动到该子节点继续处理下一个字符。 最后检查当前节点的 isEndOfWord 属性返回它的值表示是否找到了一个完整的单词。
