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

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

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

实现词典类 WordDictionary ：

WordDictionary() 初始化词典对象
void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。

# 示例1:

输入：
["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

# 提示：

1 <= word.length <= 500
addWord 中的 word 由小写英文字母组成
search 中的 word 由 '.' 或小写英文字母组成
最多调用 50000 次 addWord 和 search

# 题解：字典树(前缀树)

# 字典树

字典树（前缀树）是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。前缀树可以用 O(∣S∣) 的时间复杂度完成如下操作，其中 ∣S∣ 是插入字符串或查询前缀的长度：

向字典树中插入字符串 word；
查询字符串 word 是否已经插入到字典树中。

# 思路与算法

WordDictionary类需要添加单词和搜索单词，可以使用字典树实现。

添加单词，直接向字典树添加即可。

搜索单词，需要考虑到字符是字母和点两种情况

如果当前字符是字母，则判断当前字符对应的子结点是否存在，如果子结点存在则移动到子结点，继续搜索下一个字符，如果子结点不存在则说明单词不存在，返回 false；
如果当前字符是点号，由于点号可以表示任何字母，因此需要对当前结点的所有非空子结点继续搜索下一个字符。

# 代码

/**
    字典树节点
 */

function Node(){
    this.children = new Array(26).fill(0)
    this.isEnd = false
}

Node.prototype.insert = function(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 Node();
        }
        node = node.children[index]
    }
    node.isEnd = true
}

var WordDictionary = function() {
    this.word = new Node();
};

/** 
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function(word) {
    this.word.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(let child of node.children){
                  if (child && dfs(index + 1, child)) {
                    return true;
                }
            }
        }
        return false
    }
    return dfs(0,this.word)
};

# 大神的一个代码

var WordDictionary = function() {
    this.map = {}
};
WordDictionary.prototype.addWord = function(word) {
    // 使用单词长度作为一个存储的标志，减少后续查询式搜索的范围
    const len = word.length
    if(!this.map[len]){
       this.map[len] = []
    }
    this.map[len].push(word)
};
WordDictionary.prototype.search = function(word) {
    const len = word.length
    const target = this.map[len]

    if(!target){
        return false
    }

    let fn = word.includes('.') ? w => new RegExp(word).test(w) : w => w === word
    return target.some(fn)
};

# 参考资料

← 208. 实现 Trie (前缀树) 212. 单词搜索 II →