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