当前位置: 首页 > news >正文

学习记录:js算法(六十一):添加与搜索单词 - 数据结构设计

文章目录

    • 添加与搜索单词 - 数据结构设计
      • 思路一
      • 思路二

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

请你设计一个数据结构,支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 WordDictionary
WordDictionary() 初始化词典对象
void addWord(word)word 添加到数据结构中,之后可以对它进行匹配
bool search(word) 如果数据结构中存在字符串与 word 匹配,则返回 true ;否则,返回 falseword 中可能包含一些 ‘.’ ,每个 . 都可以表示任何一个字母。

输入:
["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 构造函数

  1. 初始化 Trie 结构:WordDictionary构造函数初始化一个空的字典树,根节点是一个空对象{},用于后续插入和搜索操作。

addWord 方法

  1. 遍历单词:遍历给定的单词word的每一个字符char,从根节点开始。
  2. 插入字符到 Trie:对于每一个字符,如果当前节点没有对应的子节点,则创建一个新的子节点。然后,将当前节点更新为这个子节点,继续处理下一个字符。
  3. 标记单词结束:当所有字符都处理完毕后,将最后一个节点的isWord属性设为true,表示一个单词的结束。

search 方法

  1. 调用 DFS 方法:search方法接收一个可能包含通配符.的单词,然后调用dfs方法从根节点开始进行深度优先搜索。
  2. 处理字符:对于每个字符,如果字符不是通配符.,则检查当前节点是否有对应的子节点,如果有,则递归调用dfs继续搜索;如果没有,则返回false
  3. 处理通配符:如果遇到通配符.,则遍历当前节点的所有子节点,递归调用dfs方法进行搜索,如果在任一子节点的搜索中返回true,则立即返回true

dfs 方法

  1. 结束条件:如果当前索引index等于输入单词的长度,说明已经遍历完所有字符,此时如果当前节点的isWord属性为true,则返回true,表示找到匹配的单词。
  2. 非通配符处理:如果当前字符不是通配符.,检查当前节点是否有对应的子节点,如果有,则递归调用dfs方法继续搜索,否则返回false
  3. 通配符处理:如果当前字符是通配符.,遍历当前节点的所有子节点(除了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 类

  1. children:一个对象,用于存储当前节点的所有子节点。每个子节点的键是字符,值是对应的 TrieNode 实例。
  2. isEndOfWord:一个布尔值,标记当前节点是否是一个完整单词的结束。若为 true,则表示从根节点到该节点的路径形成了一个完整的单词。

WordDictionary 类

  1. constructor():初始化 WordDictionary 类时创建一个根节点 this.root,所有单词都将从这个节点开始构建。

addWord() 方法

  1. 这个方法用于将一个新单词添加到字典中。
  2. 从根节点开始遍历单词的每个字符。
  3. 如果当前字符的子节点不存在,则创建一个新的 TrieNode
  4. 移动到当前字符的子节点,继续处理下一个字符。
  5. 最后,将最后一个节点的 isEndOfWord 属性设置为 true,表示这个节点是一个完整单词的结束。

search() 方法

  1. 这个方法用于查找字典中是否存在与给定字符串匹配的单词。它调用 _searchInNode 方法来执行实际的搜索操作。

_searchInNode() 递归搜索

  1. 这个方法是递归的核心部分,负责在 Trie 中查找与给定字符串匹配的单词。
  2. 遍历 word 的每个字符。
  3. 如果字符是 “ . ”,则需要检查当前节点的所有子节点:
    • 对每个子节点,递归调用 _searchInNode 方法,传入剩余的字符串(从 i + 1 开始)。
    • 如果在任何一个子节点中找到了匹配,返回 true
    • 如果所有子节点都没有找到匹配,返回 false
  4. 如果字符不是 “ . ”,则直接查找当前字符对应的子节点:
    • 如果子节点不存在,返回 false
    • 如果子节点存在,移动到该子节点,继续处理下一个字符。
  5. 最后,检查当前节点的 isEndOfWord 属性,返回它的值,表示是否找到了一个完整的单词。

http://www.mrgr.cn/news/48177.html

相关文章:

  • 从零开始的C++之旅——红黑树及其实现
  • Navicat 17 功能简介 | SQL 美化
  • ShardingSphere-Proxy 连接实战:从 Golang 原生 SQL 到 GORM 的应用
  • java对接海康摄像头
  • centos-stream9系统安装docker
  • <C#> 无法加载 DLL“xxx.dll”: 找不到指定的模块。 (异常来自 HRESULT:0x8007007E)。
  • 02.07.-链表相交
  • 深入理解Transformer的笔记记录(精简版本)---- ELMO->GPT->BERT
  • VS Code最新版本Retome远程ssh不兼容旧服务器问题
  • 10.11 QT数据库实现学生信息的增、删、改、查
  • Android blueprint/microfactory/microfactory.bash源码分析
  • ajax请求
  • 基于SpringBoot+Vue+MySQL的留守儿童爱心网站
  • 解锁机器人视觉与人工智能的潜力,从“盲人机器”改造成有视觉能力的机器人(下)
  • java医院后台管理系统设计与实现源码(springboot+vue+mysql)
  • 消息中间件介绍
  • 如何快速保存微信公众号文章中的图片
  • 【JVM】JMM
  • 介绍Java
  • 《浔川社团官方自即日起停止发文》
  • 大数据治理快速入门指南
  • kali(专业的渗透测试虚拟机)|kali下载链接地址 |kali安装 |kali部署指南
  • GitHub Universe Learn Live|共聚 2024 GitHub Universe 十周年
  • postgresql 安装
  • 10.11Python数学基础-多维随机变量及其分布
  • 物理学基础精解【71】