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

题目

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/design-add-and-search-words-data-structure
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

请你设计一个数据结构,支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 

实现词典类 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"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

思路(字典树)

其实就类似于哈夫曼树的前缀编码,每一层有26种可能性,尽头的节点的isEnd设置为true,因为没有一个编码是另外一个编码的前缀,所以称为前缀编码

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

 答案

var WordDictionary = function() {
    this.trieRoot = new TrieNode();
};

/** 
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function(word) {
    this.trieRoot.insert(word);
};

/** 
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function (word) {
    const dfs = (index, node) => {
        if (index === word.length) {
            return node.isEnd;
        }
        const ch = word[index];
        if (ch !== '.') {
            const child = node.children[ch.charCodeAt() - 'a'.charCodeAt()]
            if (child && dfs(index + 1, child)) {
                return true;
            }
        } else {
            for (const child of node.children) {
                if (child && dfs(index + 1, child)) {
                    return true;
                }
            }
        }
        return false;
    }

    return dfs(0, this.trieRoot);
};
class TrieNode{
    constructor() {
        this.children=new Array(26).fill(0);
        this.isEnd=false;
    }

    insert(word) {
        let node=this;
        for(let i=0;i<word.length;i++)
        {
            const ch=word[i];
            const index=ch.charCodeAt()-'a'.charCodeAt();
            if(node.children[index] === 0){
                node.children[index]=new TrieNode();
            }
            node=node.children[index]
        }
        node.isEnd=true;
    }

    getChildren() {
        return this.children;
    }

    isEnd() {
        return this.isEnd;
    }
}
/**
 * Your WordDictionary object will be instantiated and called as such:
 * var obj = new WordDictionary()
 * obj.addWord(word)
 * var param_2 = obj.search(word)
 */

上一篇:Carrot2 在线版 知识图谱:以慢性胰腺炎为例


下一篇:chromedp的使用 案例 二