https://blog.csdn.net/m0_46202073/article/details/107253959
https://leetcode.cn/problems/implement-trie-prefix-tree/solution/trie-tree-de-shi-xian-gua-he-chu-xue-zhe-by-huwt/

208. 实现 Trie (前缀树)

  1. /*
  2.  * @lc app=leetcode.cn id=208 lang=javascript
  3.  *
  4.  * [208] 实现 Trie (前缀树)
  5.  */
  7. // @lc code=start
  9. var TrieNode =function(){        // 节点
  10.     this.isEnd = false;
  11.     this.next = Array(26);    
  12. }
  14. var Trie = function () {  // 前缀树
  15.     this.node= new TrieNode();
  16. };
  18. /**
  19.  * @param {string} word
  20.  * @return {void}
  21.  */
  22. Trie.prototype.insert = function (word) {
  23.     let node = this.node;
  24.     for (let w of word) {
  25.         const index = w.charCodeAt() - 'a'.charCodeAt()
  26.         if (!node.next[index]) {
  27.             node.next[index] = new Trie();
  28.         }
  29.         node = node.next[index]
  30.     }
  31.     node.isEnd = true;
  32. };
  34. /**
  35.  * @param {string} word
  36.  * @return {boolean}
  37.  */
  38. Trie.prototype.search = function (word) {
  39.     let node = this;
  40.     for (let w of word) {
  41.         const index = w.charCodeAt() - 'a'.charCodeAt()
  42.         if (!node.next[index]) return false;
  43.         node = node.next[index]
  44.     }
  45.     return node.isEnd
  46. };
  48. /**
  49.  * @param {string} prefix
  50.  * @return {boolean}
  51.  */
  52. Trie.prototype.startsWith = function (prefix) {
  53.     let node = this;
  54.     for (let w of prefix) {
  55.         const index = w.charCodeAt() - 'a'.charCodeAt()
  56.         if (!node.next[index]) return false;
  57.         node = node.next[index]
  58.     }
  59.     return true;
  60. };
  62. /**
  63.  * Your Trie object will be instantiated and called as such:
  64.  * var obj = new Trie()
  65.  * obj.insert(word)
  66.  * var param_2 = obj.search(word)
  67.  * var param_3 = obj.startsWith(prefix)
  68.  */
  69. // @lc code=end

820. 单词的压缩编码

  1. var minimumLengthEncoding = function (words) {
  2.     words.sort((a, b) => { //需要先排序，让长的单词先插入
  3.         return b.length - a.length;
  4.     })
  5.     let sum = 0;
  6.     let trie = new Trie();
  7.     for (let word of words) {
  8.         sum += trie.insert(word);
  9.     }
  10.     return sum;
  11. };
  13. var TrieNode =function(){        // 节点
  14.     this.next = Array(26);    
  15. }
  17. class Trie {
  18.     constructor() {
  19.         this.node= new TrieNode();
  20.     }
  21.     insert(word) {
  22.         let node = this.node;
  23.         let flag = false;
  24.         for (let i = word.length - 1; i >= 0; i--) { //倒着插入
  25.             const index = word[i].charCodeAt() - 'a'.charCodeAt();
  26.             if (!node.next[index]) {
  27.                 flag = true; //如果有新建节点则
  28.                 node.next[index] = new TrieNode();
  29.             }
  30.             node = node.next[index];
  31.         }
  32.         return flag ? word.length + 1 : 0;
  33.     }
  34. }

211. 添加与搜索单词 - 数据结构设计

前几道题的search都是迭代的方式，这有一点弊端：“cur一条路走到黑”，但有时我们需要走一个分叉的路，去尝试更多的可能。
所以接下来用递归的方式去搜索。

  1. var TrieNode = function () {
  2.     this.next = Array(26);
  3.     this.isEnd = false;
  4. }
  6. var WordDictionary = function () {
  7.     this.node = new TrieNode();
  8. };
  10. /**
  11.  * @param {string} word
  12.  * @return {void}
  13.  */
  14. WordDictionary.prototype.addWord = function (word) {
  15.     let node = this.node;
  16.     for (let w of word) {
  17.         const index = w.charCodeAt() - 'a'.charCodeAt();
  18.         if (!node.next[index]) {
  19.             node.next[index] = new TrieNode();
  20.         }
  21.         node = node.next[index];
  22.     }
  23.     node.isEnd = true;
  24. };
  26. /**
  27.  * @param {string} word
  28.  * @return {boolean}
  29.  */
  30. WordDictionary.prototype.search = function (word) {
  31.     return match(word, this.node, 0);
  32. };
  35. function match(word, node, start) {
  36.     if (start === word.length) {
  37.         return node.isEnd;
  38.     }
  39.     if (word[start] === '.') {
  40.         for (let i = 0; i < 26; i++) {
  41.             if (node.next[i] != null && match(word, node.next[i], start + 1)) {
  42.                 return true;
  43.             }
  44.         }
  45.         return false;
  46.     } else {
  47.         const index = word[start].charCodeAt() - 'a'.charCodeAt();
  48.         return node.next[index] != null && match(word, node.next[index], start + 1)
  49.     }
  51. }

676. 实现一个魔法字典

与211题类似，

  1. var TrieNode = function () {
  2.     this.next = Array(26);
  3.     this.isEnd = false;
  4. }
  6. var MagicDictionary = function () {
  7.     this.node = new TrieNode();
  8. };
  10. /**
  11.  * @param {string[]} dictionary
  12.  * @return {void}
  13.  */
  14. MagicDictionary.prototype.buildDict = function (dictionary) {
  15.     for (let dic of dictionary) {
  16.         let node = this.node;
  17.         for (let w of dic) {
  18.             const index = w.charCodeAt() - 'a'.charCodeAt();
  19.             if (!node.next[index]) {
  20.                 node.next[index] = new TrieNode();
  21.             }
  22.             node = node.next[index];
  23.         }
  24.         node.isEnd = true;
  25.     }
  26. };
  28. /**
  29.  * @param {string} searchWord
  30.  * @return {boolean}
  31.  */
  32. MagicDictionary.prototype.search = function (searchWord) {
  33.     return match(searchWord, this.node, 0, true)
  34. };
  36. var match = function (word, node, start, hasChance) {
  37.     if (start === word.length) {
  38.         return node.isEnd && !hasChance;
  39.     }
  40.   //这样写，当字典树中有"hello"和"hallo"时，search("hello")会返回false。
  41.     // const index = word[start].charCodeAt() - 'a'.charCodeAt();
  42.     // if (!node.next[index]) {
  43.     //     if (hasChance) {
  44.     //         for (let i = 0; i < 26; i++) {
  45.     //             if (node.next[i] != null && match(word, node.next[i], start + 1, false)) {
  46.     //                 return true;
  47.     //             }
  48.     //         }
  49.     //     }
  50.     //     return false;
  51.     // } else {
  52.     //     return match(word, node.next[index], start + 1, hasChance)
  53.     // }
  54.   // 所以改为一次for(26)的遍历。
  55.     for (let i = 0; i < 26; i++) {
  56.         if (node.next[i]) {
  57.             const index = word[start].charCodeAt() - 'a'.charCodeAt();
  58.             if (index === i && match(word, node.next[i], start + 1, hasChance)) {
  59.                 return true;
  60.             } else if (index !== i && hasChance && match(word, node.next[i], start + 1, false)) {
  61.                 return true;
  62.             }
  63.         }
  64.     }
  65.     return false;
  66. }

面试题 17.13. 恢复空格