Topic describes

Design a data structure that supports the following two operations

1) void addWord (word)

2) bool search (word)

3) Search (word) can search text or regular expression strings, strings contain only letters. Or a – z

4). Can represent any letter

The sample

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") - >false
search("bad") - >true
search(".ad") - >true
search("b..") - >true
Copy the code

Note: the re in the problem is limited to the symbol ‘.’, so don’t complicate the problem

Train of thought

1. Define a constructor whose object property is the object that stores Word {}

2. To facilitate quick search, the length of words is used as the key

3. Add the functions addWord and search to the prototype

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
    // The search needs to determine whether it is a regular string or not
    
    const arr = this.words[length]
    
    if(key.indexOf('. ') = = = -1) {
        // A common character string
      returnarr.indexOf(key) ! = = -1
    }
    
    / / regular
    const reg = new RegExp(key)
    
    return arr.some(item= > reg.test(item))
}



Copy the code