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

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

实现词典类 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

提示：

• 1 <= word.length <= 25
• addWord 中的 word 由小写英文字母组成
• search 中的 word 由 '.' 或小写英文字母组成

var WordDictionary = function() {
    this.dictTree = {};
};

/** 
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function(word) {
    let node = this.dictTree
    for(let ch of word){
        node[ch] ??= {};
        node = node[ch];
    }
    node.isEnd = true;
};

/** 
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function(word) {
    let len = word.length;
    const searchNode = (node, start)=>{
        let i=start, end = word.indexOf('.', start), noDot = false;
        if(end==-1){
            end = len;
            noDot = true;
        }
        for(; i<end; i++){
            const ch = word[i];
            if(!node[ch]){
                return false;
            }
            node = node[ch];
        }
        if(noDot){
            return 'isEnd' in node;
        }
        let keys = Object.keys(node);
        for(let k of keys){
            if(k == 'isEnd'){
                continue;
            }
            if(searchNode(node[k], i+1)){
                return true;
            }
        }
        return false;
    }
    return searchNode(this.dictTree, 0);
};

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