题目描述

真题描述： 设计一个支持以下两种操作的数据结构

1）void addWord(word)

2）bool search(word)

3）search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z

4）. 可以表示任何一个字母

示例

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
复制代码

注意：题目中的正则仅限于有个符号’.’，不要把题目想复杂了

思路

1.定义一个构造函数，对象属性为存储word的对象{}

2.为了方便快速查找，以words的length作为key来存储

3.原型上添加函数addWord和search

function WordDictionary() {
    this.words = {}
}

WordDictionary.prototype.addWord = function(word) {
    const length = word.length
    if(this.words[length] !== undefined) {
        this.words[length].push(word)
    } else {
        this.words[length] = [word]
    }
    
}

WordDictionary.prototype.search = function(key) {
    const length = key.length
    
    if(this.words[length] === undefined) return false
    // 搜索需要判断是正则还是普通字符串
    
    const arr = this.words[length]
    
    if(key.indexOf('.') === -1) {
        // 普通字符串
      return arr.indexOf(key) !== -1
    }
    
    // 正则
    const reg = new RegExp(key)
    
    return arr.some(item => reg.test(item))
}



复制代码