美文网首页
211. Design Add and Search Words

211. Design Add and Search Words

作者: jluemmmm | 来源:发表于2021-10-10 18:31 被阅读0次

    添加与搜索单词,数据结构设计。

    Trie 称为数字树或前缀树,是一种搜索有序树数据结构,主要用于对字符串进行高效的动态添加/搜索操作。

    应用:自动完成搜索、拼写检查、T9预测文本,IP路由(最长前缀匹配)等。

    如果用hash实现的情况下,时间复杂度O(m * n)。大型数据集的缩放,一旦哈希表的增加,会有很多哈希冲突,搜索时间复杂度可以增加到 O(n ^ 2 * m),当存储具有许多相同前缀的键时,与hashmap相比,Trie可以使用更少的空间。

    参考208,递归实现

    • 时间复杂度O(n),空间复杂度O(1)
    • Runtime: 204 ms, faster than 94.91%
    • Memory Usage: 60.1 MB, less than 53.40%
    
    var WordDictionary = function() {
      this.map = {};
    };
    
    /** 
     * @param {string} word
     * @return {void}
     */
    WordDictionary.prototype.addWord = function(word) {
      let node = this.map;
      for (const ch of word) {
        if (!node[ch]) {
          node[ch] = {};
        }
        node = node[ch];
      }
      node.isEnd = true;
      // console.log(this.map)
    };
    
    /** 
     * @param {string} word
     * @return {boolean}
     */
    WordDictionary.prototype.search = function(word) {
      return this.searchInNode(word, this.map);
    };
    
    
    WordDictionary.prototype.searchInNode = function(word, node) {
      for (let i = 0; i < word.length; i++) {
        const ch = word[i];
        if (!node[ch]) {
          if (ch === '.') {
            for (let j in node) {
              if (this.searchInNode(word.substring(i + 1), node[j])) {
                return true;
              }
            }
          }
          return false;
        } else {
          node = node[ch];
        }
      }
      return node !== undefined && node.isEnd !== undefined;
    };
    
    /** 
     * Your WordDictionary object will be instantiated and called as such:
     * var obj = new WordDictionary()
     * obj.addWord(word)
     * var param_2 = obj.search(word)
     */
    

    相关文章

      网友评论

          本文标题:211. Design Add and Search Words

          本文链接:https://www.haomeiwen.com/subject/cuzonltx.html