前缀树

前缀树次要用来解决与字符串查找相干的问题。如果字符串的长度为 k，因为在前缀树中查找一个字符串相当于顺着前缀树的门路查找字符串的每个字符，因而工夫复杂度是 O（k）。

在哈希表中，只有输出残缺的字符串能力进行查找操作，在前缀树中就没有这个限度。例如，能够只输出字符串的后面若干字符，即前缀，查找以这个前缀结尾的所有字符串。如果要求依据字符串的前缀进行查找，那么正当利用前缀树可能是解决这个问题的要害。

62. 实现前缀树

/**
 * Initialize your data structure here.
 */
var Trie = function() {this.children = {}; 
};

/**
 * Inserts a word into the trie. 
 * @param {string} word
 * @return {void}
 */
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.searchPrefix = function(prefix) {
     let node = this.children;
     for (const ch of prefix) {if(!node[ch]) {return false}
        node = node[ch]
     }
      return node;
}

/**
 * Returns if the word is in the trie. 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {const node = this.searchPrefix(word)
    return node !== undefined && node.isEnd !== undefined;
};

/**
 * Returns if there is any word in the trie that starts with the given prefix. 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {return this.searchPrefix(prefix);
};

63. 替换单词

英语中有一个概念叫词根。在词根前面加上若干字符就能拼出更长的单词。例如，”an” 是一个词根，在它前面加上 ”other” 就能失去另一个单词 ”another”。当初给定一个由词根组成的字典和一个英语句子，如果句子中的单词在字典中有它的词根，则用它的词根替换该单词；如果单词没有词根，则保留该单词。请输入替换后的句子。例如，如果词根字典蕴含字符串[“cat”，”bat”，”rat”]，英语句子为 ”the cattle was rattled by the battery”，则替换之后的句子是 ”the cat was rat by the bat”。

/**
 * @param {string[]} dictionary
 * @param {string} sentence
 * @return {string}
 */
var replaceWords = function(dictionary, sentence) {let children = {}
    // 构建前缀树
    for(let word of dictionary) {
        let node = children;
        for(let ch of word) {if(!node[ch]) {node[ch] = {}}
            node = node[ch]
        }
        node.isEnd = true
    }

    return sentence.split(' ').map(word => {
        let node = children, tmp = ''
        for (let w of word) {node = node[w]
            tmp += w
            if (!node || node.isEnd) break          
        }
        return node && node.isEnd ? tmp : word
    }).join(' ')

};

64. 神奇的字典

题目：请实现有如下两个操作的神奇字典。
● 函数 buildDict，输出单词数组用来创立一个字典
● 函数 search，输出一个单词，判断是否批改该单词中的一个字符，使批改之后的单词是字典中的一个单词。

/**
 * Initialize your data structure here.
 */
var MagicDictionary = function() {this.dictionary = []
};

/** 
 * @param {string[]} dictionary
 * @return {void}
 */
MagicDictionary.prototype.buildDict = function(dictionary) {this.dictionary = dictionary};

/** 
 * @param {string} searchWord
 * @return {boolean}
 */
MagicDictionary.prototype.search = function(searchWord) {for (const dict of this.dictionary) {if (dict.length == searchWord.length) {
            let diff = 0
            for (let i = 0; i < dict.length; i++) {if (dict[i] != searchWord[i]) diff++
                if (diff > 1) break
            }
            if (diff == 1) return true
        }
    }
    return false
};

65. 最短的单词编码

单词数组 words 的 无效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：
words.length == indices.length
助记字符串 s 以 ‘#’ 字符结尾
对于每个下标 indices[i]，s 的一个从 indices[i] 开始、到下一个 ‘#’ 字符完结（但不包含 ‘#’）的 子字符串 恰好与 words[i] 相等

/**
 * @param {string[]} words
 * @return {number}
 */
var minimumLengthEncoding = function(words) {const set = new Set(words)
    for (const word of set) {for (let i = 1; i < word.length; i++) set.delete(word.substring(i))
    }
    let sum = 0
    for (const word of set) {sum += word.length + 1}
    return sum
};

66. 单词之和

/**
 * Initialize your data structure here.
 */
var MapSum = function() {this.map = new Map();
    this.prefixmap = new Map();};

/** 
 * @param {string} key 
 * @param {number} val
 * @return {void}
 */
MapSum.prototype.insert = function(key, val) {
    // 防止反复
    const delta = val - (this.map.get(key) || 0);
    this.map.set(key, val);
    for (let i = 1; i <= key.length; ++i) {const currprefix = key.substring(0, i);
        this.prefixmap.set(currprefix, (this.prefixmap.get(currprefix) || 0) + delta);
    }
};

/** 
 * @param {string} prefix
 * @return {number}
 */
MapSum.prototype.sum = function(prefix) {return this.prefixmap.get(prefix) || 0;
};

67. 最大的异或

这个是真的难，思路转换很微妙

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaximumXOR = function(nums) {const tree={};
    for(let i=0;i<nums.length;i++){
        let node=tree;
        for(let j=30;j>=0;j--){let attr=(nums[i]>>j)&1;
            if(!node[attr]){node[attr]={};}
            node=node[attr];
        }
    }
    let max=0;
    for(let i=0;i<nums.length;i++){
        let node=tree;
        let result=0;
        for(let j=30;j>=0;j--){let bit=(nums[i]>>j)&1;
            let index=bit^1;
            if(node[index]){result|=(1<<j);
                node=node[index];
            }
            else{node=node[bit];
            }
        }
        max=Math.max(max,result);
    }
    return max;
};

总结

前缀树通常用来保留字符串，它的节点和字符串的字符对应，而门路和字符串对应。如果只思考英文小写字母，那么前缀树的每个节点有 26 个子节点。为了标注某些节点和字符串的最初一个字符对应，前缀树节点中通常须要一个布尔类型的字段。

前缀树常常用来解决与字符串查找相干的问题。和哈希表相比，在前缀树中查找更灵便。既能够从哈希表中找出所有以某个前缀结尾的所有单词，也能够找出批改了一个（或多个）字符的字符串。

应用前缀树解决问题通常须要两步：第 1 步是创立前缀树，第 2 步是在前缀树中查找。