大厂算法面试之leetcode精讲22.字典树 leetcode个人解题总结

大厂算法面试之leetcode精讲22.字典树视频讲解（高效学习）:点击学习目录： 1.开篇介绍
2.时间空间复杂度
3.动态规划
4.贪心
5.二分查找
6.深度优先&广度优先
7.双指针
8.滑动窗口
9.位运算
10.递归&分治
11剪枝&回溯
12.堆
13.单调栈
14.排序算法
15.链表
16.set&map
17.栈
18.队列
19.数组
20.字符串
21.树
22.字典树
23.并查集
24.其他类型题
Trie树，即字典树，又称前缀树，是一种树形结构，典型应用是用于统计和排序大量的字符串（但不限于字符串），所以经常被搜索引擎用于文本词频统计。它的优先是，最大限度的减少无谓的字符串比较，提高查找效率。
Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销，以达到提高效率的目的
基本性质

根节点不包含字符，除跟节点外每个节点都只包含一个字符
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串
每个节点的所有子节点包含的字符都不相同

文章图片

实际应用，例如搜索

文章图片

208. 实现 Trie (前缀树)(medium)

文章图片

思路：本题这字符集长度是26，即26个小写英文字母，isEnd表示该节点是否是字符串的结尾。
1. 插入字符串：从字段树的根节点开始，如果子节点存在，继续处理下一个字符，如果子节点不存在，则创建一个子节点到children的相应位置，沿着指针继续向后移动，处理下一个字符，以插入‘cad’为例
2. 查找前缀：从根节点开始，子节点存在，则沿着指针继续搜索下一个子节点，直到最后一个，如果搜索到了前缀所有字符，说明字典树包含该前缀。子节点不存在就说明字典树中不包含该前缀，返回false。
3. 查找字符串：和查找前缀一样，只不过最后返回的节点的isEnd是true，也就是说字符串正好是字典树的一个分支
复杂度分析：时间复杂度，初始化为 O(1)，其余操作为 O(S)，s为字符串的长度。空间复杂度为O(T)，T为字符集的大小，本题是26

js:

var Trie = function() { this.children = {}; }; Trie.prototype.insert = function(word) { let nodes = this.children; for (const ch of word) {//循环word if (!nodes[ch]) {//当前字符不在子节点中则创建一个子节点到children的响应位置 nodes[ch] = {}; } nodes = nodes[ch]; //移动指针到下一个字符子节点 } nodes.isEnd = true; //字符是否结束 }; Trie.prototype.searchPrefix = function(prefix) { let nodes = this.children; for (const ch of prefix) {//循环前缀 if (!nodes[ch]) {//当前字符不在子节点中直接返回false return false; } nodes = nodes[ch]; //移动指针到下一个字符子节点 } return nodes; //返回最后的节点 }Trie.prototype.search = function(word) { const nodes = this.searchPrefix(word); //判断searchPrefix返回的节点是不是字符串的结尾的字符 return nodes !== undefined && nodes.isEnd !== undefined; }; Trie.prototype.startsWith = function(prefix) { return this.searchPrefix(prefix); };

Java:

//java class Trie { private Trie[] children; private boolean isEnd; public Trie() { children = new Trie[26]; isEnd = false; }public void insert(String word) { Trie node = this; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); int index = ch - 'a'; if (node.children[index] == null) { node.children[index] = new Trie(); } node = node.children[index]; } node.isEnd = true; }public boolean search(String word) { Trie node = searchPrefix(word); return node != null && node.isEnd; }public boolean startsWith(String prefix) { return searchPrefix(prefix) != null; }private Trie searchPrefix(String prefix) { Trie node = this; for (int i = 0; i < prefix.length(); i++) { char ch = prefix.charAt(i); int index = ch - 'a'; if (node.children[index] == null) { return null; } node = node.children[index]; } return node; } }

212. 单词搜索 II (hard)

文章图片

思路：将words数组中的所有字符串加入Trie中，然后遍历网格，判断网格路径形成的字符串在不在Trie中，然后上下左右四个方向不断回溯尝试。
复杂度分析：时间复杂度O(MN?3^L)，空间复杂度是O(max(MN, KL))，visited空间是O(MN)，字典树O(KL)，L是最长字符串的长度，K是words数组的长度。dfs递归栈的最大深度是O(min(L,MN))，

方法1.Trie Js:

var findWords = function (board, words) { const trie = new Trie(); const dxys = [ [0, -1], [-1, 0], [0, 1], [1, 0], ]; const xLen = board.length, yLen = board[0].length; const visited = {}; const ret = []; // 构建Trie for (let word of words) { trie.insert(word); }// DFS board const dfs = (x, y, nodes, str) => { if (nodes[board[x][y]].isEnd) { ret.push(str + board[x][y]); // 置为false是为了防止重复将字符串加入到ret中 nodes[board[x][y]].isEnd = false; }// 处理本层状态 nodes = nodes[board[x][y]]; str += board[x][y]; // 向四联通方向检索 visited[x * 100 + y] = true; for (let [dx, dy] of dxys) { const newX = x + dx, newY = y + dy; if ( newX < 0 || newY < 0 || newX >= xLen || newY >= yLen || !nodes[board[newX][newY]] || visited[newX * 100 + newY] ) continue; dfs(newX, newY, nodes, str); } visited[x * 100 + y] = false; }; for (let x = 0; x < xLen; x++) { for (let y = 0; y < yLen; y++) { if (trie.children[board[x][y]]) dfs(x, y, trie.children, ""); } }return ret; }; var Trie = function () { this.children = {}; }; Trie.prototype.insert = function (word) { let nodes = this.children; for (const ch of word) {//循环word if (!nodes[ch]) {//当前字符不在子节点中则创建一个子节点到children的响应位置 nodes[ch] = {}; } nodes = nodes[ch]; //移动指针到下一个字符 } nodes.isEnd = true; //字符是否结束 };

Java:

class Solution { int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; public List findWords(char[][] board, String[] words) { Trie trie = new Trie(); for (String word : words) { trie.insert(word); }Set ans = new HashSet(); for (int i = 0; i < board.length; ++i) { for (int j = 0; j < board[0].length; ++j) { dfs(board, trie, i, j, ans); } }return new ArrayList(ans); }public void dfs(char[][] board, Trie now, int i1, int j1, Set ans) { if (!now.children.containsKey(board[i1][j1])) { return; } char ch = board[i1][j1]; now = now.children.get(ch); if (!"".equals(now.word)) { ans.add(now.word); }board[i1][j1] = '#'; for (int[] dir : dirs) { int i2 = i1 + dir[0], j2 = j1 + dir[1]; if (i2 >= 0 && i2 < board.length && j2 >= 0 && j2 < board[0].length) { dfs(board, now, i2, j2, ans); } } board[i1][j1] = ch; } }class Trie { String word; Map children; boolean isWord; public Trie() { this.word = ""; this.children = new HashMap(); }public void insert(String word) { Trie cur = this; for (int i = 0; i < word.length(); ++i) { char c = word.charAt(i); if (!cur.children.containsKey(c)) { cur.children.put(c, new Trie()); } cur = cur.children.get(c); } cur.word = word; } }

720. 词典中最长的单词 (easy) 方法1：sort+hash

思路：排序数组，然后遍历字符串数组，判断数组中的每个字符串的子串是否都在数组中
复杂度：时间复杂度O(mn)，m是字符串数组的长度,n是字符串最大长度。空间复杂度O(m)

【大厂算法面试之leetcode精讲22.字典树】js：

var longestWord = function (words) { let set = new Set() words.forEach(v => set.add(v))//set方便查找 //先按长度排序，在按字典序 words.sort((a, b) => a.length === b.length ? a.localeCompare(b) : b.length - a.length) for (let i = 0; i < words.length; i++) { let flag = true for (let j = 1; j < words[i].length; j++) { if (!set.has(words[i].substring(0, j))) {//查看set中是否有该字符串的每个子串 flag = false break } } if (flag) { return words[i] } } return '' };

java:

class Solution { public String longestWord(String[] words) { Set wordset = new HashSet(); for (String word: words) wordset.add(word); Arrays.sort(words, (a, b) -> a.length() == b.length() ? a.compareTo(b) : b.length() - a.length()); for (String word: words) { boolean flag = true; for (int k = 1; k < word.length(); ++k) { if (!wordset.contains(word.substring(0, k))) { flag = false; break; } } if (flag) return word; }return ""; } }

方法2:字典树

文章图片

思路：将所有字符串插入trie中，递归寻找那个长度最大的单词
复杂度：时间复杂度O(mn)，m是字符串数组的长度,n是字符串最大长度。空间复杂度O(∑w)。递归深度不会超过最长单词长度,字段书的空间复杂度是所有字符串的长度和。

js:

var longestWord = function (words) { const trie = new Trie() words.forEach(word => {//将所有字符串插入trie中 trie.insert(word) }) let res = '' const _helper = (nodes, path) => { if (path.length > res.length || (res.length === path.length && res > path)) { res = path } //{a:{b1:{c1:{isEnd: true}},b2:{c2:{isEnd: true}}}} for (const [key, value] of Object.entries(nodes)) { if (value.isEnd) {//如果当前字符是某一个字符串的结尾 path += key _helper(value, path)//递归寻找 path = path.slice(0, -1)//回溯 } } } _helper(trie.children, '')//递归寻找那个长度最大的单词 return res }var Trie = function() { this.children = {}; }; Trie.prototype.insert = function(word) { let nodes = this.children; for (const ch of word) {//循环word if (!nodes[ch]) {//当前字符不在子节点中则创建一个子节点到children的响应位置 nodes[ch] = {}; } nodes = nodes[ch]; //移动指针到下一个字符 } nodes.isEnd = true; //字符是否结束 };