215

题目

暴力破解法

var Trie = function() {
    this.arr = [];
    this.map = new Map();
};

Trie.prototype.insert = function(word) {
    this.arr.push(word);
    this.map.set(word,word);
};

Trie.prototype.search = function(word) {
    return this.map.get(word)!==undefined;
};

Trie.prototype.startsWith = function(prefix) {
    for(let i=0,len=this.arr.length;i<len;i++){
        if(this.arr[i].indexOf(prefix)===0)return true;
    }
    return false;
};

前缀树

var Trie = function() {
  this.children = {};
};

Trie.prototype.insert = function(word) {
  let node = this.children;
  for(const ch of word){
    if(!node[ch]){
      node[ch] = {}
    }
    node = node[ch];
  }
  node.isEnd = true;
};

Trie.prototype.search = function(word) {
  const node = this.searchPrefix(word);
  return node!==undefined && node.isEnd !== undefined;
};

Trie.prototype.startsWith = function(prefix) {
  let node = this.searchPrefix(prefix)
  return node !== undefined && node;
};

Trie.prototype.searchPrefix = function(prefix){
  let node = this.children;
  for(const ch of prefix){
    if(!node[ch]){
      return false;
    }
    node = node[ch];
  }
  return node;
}