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

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

请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 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 构造函数

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 属性，返回它的值，表示是否找到了一个完整的单词。