211. 添加与搜索单词 - 数据结构设计（JS实现）

港控/mmm° 2022-11-25 13:07 89阅读 0赞

## 1 题目 ##

> 设计一个支持以下两种操作的数据结构：  
> void addWord(word)  
> bool search(word)  
> search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。  
> 示例:  
> addWord(“bad”)  
> addWord(“dad”)  
> addWord(“mad”)  
> search(“pad”) -> false  
> search(“bad”) -> true  
> search(".ad") -> true  
> search(“b…”) -> true  
> 说明:  
> 你可以假设所有单词都是由小写字母 a-z 组成的。

链接：https://leetcode-cn.com/problems/add-and-search-word-data-structure-design

## 2 思路 ##

**这道题还是用字典树的方法来存储单词，每个节点维护一个指针数组，搜索时若遇到小数点，则递归遍历当前数组所有指针进行下一步搜索**

## 3代码 ##

/** * Initialize your data structure here. */
    var WordDictionary = function() { 
        this.startIndex = 'a'.charCodeAt();
        this.root = new Node();
    };
    
    /** * Adds a word into the data structure. * @param {string} word * @return {void} */
    WordDictionary.prototype.addWord = function(word) { 
        if (word.length === 0) return;
    
        let p = this.root;
        for (let letter of word) { 
            let index = letter.charCodeAt() - this.startIndex;
            if (!p.list[index]) { 
                p.list[index] = new Node();
            }
    
            p = p.list[index];
        }
    
        p.word = word;
    };
    
    /** * Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. * @param {string} word * @return {boolean} */
    WordDictionary.prototype.search = function(word) { 
        if (word.length === 0) return false;
    
        return this.d(this.root, word);
    
    };
    
    WordDictionary.prototype.d = function(p, word) { 
       if (!p) return false;
       if (word === '') return !!p.word;
       
       let letter = word[0];
        
       if (letter === '.') { 
           for (let i=0; i<p.list.length; i++) { 
               if (p.list[i] && this.d(p.list[i], word.slice(1))) { 
                   return true;
               }
           }
           return false;
       } else { 
           let index = letter.charCodeAt() - this.startIndex;
           p = p.list[index];
           return this.d(p, word.slice(1));
       }
    }
    
    function Node() { 
        this.list = [];
        this.word = null;
    }
    
    /** * Your WordDictionary object will be instantiated and called as such: * var obj = new WordDictionary() * obj.addWord(word) * var param_2 = obj.search(word) */