大廠算法面試之leetcode精講22.字典樹
視頻講解（高效學(xué)習(xí)）:點(diǎn)擊學(xué)習(xí)
目錄：
Trie樹廷支，即字典樹次兆，又稱前綴樹逗概，是一種樹形結(jié)構(gòu)蔬胯，典型應(yīng)用是用于統(tǒng)計(jì)和排序大量的字符串（但不限于字符串），所以經(jīng)常被搜索引擎用于文本詞頻統(tǒng)計(jì)蛹稍。它的優(yōu)先是吧黄，最大限度的減少無(wú)謂的字符串比較，提高查找效率稳摄。
Trie的核心思想是空間換時(shí)間稚字，利用字符串的公共前綴來(lái)降低查詢時(shí)間的開(kāi)銷，以達(dá)到提高效率的目的
基本性質(zhì)
- 根節(jié)點(diǎn)不包含字符，除跟節(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)都只包含一個(gè)字符
- 從根節(jié)點(diǎn)到某一個(gè)節(jié)點(diǎn)胆描，路徑上經(jīng)過(guò)的字符連接起來(lái)瘫想，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串
- 每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同
<img src="https://gitee.com/xiaochen1024/assets/raw/master/assets/20211118161003.png" alt="ds_8" style="zoom:50%;" />
實(shí)際應(yīng)用，例如搜索
ds_7
208. 實(shí)現(xiàn) Trie (前綴樹)(medium)
<img src="https://gitee.com/xiaochen1024/assets/raw/master/assets/20211118161003.png" alt="ds_8" style="zoom:50%;" />
- 思路：本題這字符集長(zhǎng)度是26昌讲，即26個(gè)小寫英文字母国夜，isEnd表示該節(jié)點(diǎn)是否是字符串的結(jié)尾。
- 插入字符串：從字段樹的根節(jié)點(diǎn)開(kāi)始短绸，如果子節(jié)點(diǎn)存在车吹，繼續(xù)處理下一個(gè)字符，如果子節(jié)點(diǎn)不存在醋闭，則創(chuàng)建一個(gè)子節(jié)點(diǎn)到children的相應(yīng)位置窄驹，沿著指針繼續(xù)向后移動(dòng)，處理下一個(gè)字符证逻，以插入‘cad’為例
- 查找前綴：從根節(jié)點(diǎn)開(kāi)始乐埠，子節(jié)點(diǎn)存在，則沿著指針繼續(xù)搜索下一個(gè)子節(jié)點(diǎn)囚企，直到最后一個(gè)丈咐，如果搜索到了前綴所有字符，說(shuō)明字典樹包含該前綴龙宏。子節(jié)點(diǎn)不存在就說(shuō)明字典樹中不包含該前綴棵逊，返回false。
- 查找字符串：和查找前綴一樣银酗，只不過(guò)最后返回的節(jié)點(diǎn)的isEnd是true辆影，也就是說(shuō)字符串正好是字典樹的一個(gè)分支
- 復(fù)雜度分析：時(shí)間復(fù)雜度，初始化為
O(1)黍特，其余操作為O(S)秸歧，s為字符串的長(zhǎng)度⌒瞥海空間復(fù)雜度為O(T)，T為字符集的大小谬墙，本題是26
js:
var Trie = function() {
this.children = {};
};
Trie.prototype.insert = function(word) {
let nodes = this.children;
for (const ch of word) {//循環(huán)word
if (!nodes[ch]) {//當(dāng)前字符不在子節(jié)點(diǎn)中 則創(chuàng)建一個(gè)子節(jié)點(diǎn)到children的響應(yīng)位置
nodes[ch] = {};
}
nodes = nodes[ch];//移動(dòng)指針到下一個(gè)字符子節(jié)點(diǎn)
}
nodes.isEnd = true;//字符是否結(jié)束
};
Trie.prototype.searchPrefix = function(prefix) {
let nodes = this.children;
for (const ch of prefix) {//循環(huán)前綴
if (!nodes[ch]) {//當(dāng)前字符不在子節(jié)點(diǎn)中 直接返回false
return false;
}
nodes = nodes[ch];//移動(dòng)指針到下一個(gè)字符子節(jié)點(diǎn)
}
return nodes;//返回最后的節(jié)點(diǎn)
}
Trie.prototype.search = function(word) {
const nodes = this.searchPrefix(word);
//判斷searchPrefix返回的節(jié)點(diǎn)是不是字符串的結(jié)尾的字符
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)
ds_84
- 思路：將words數(shù)組中的所有字符串加入Trie中今布，然后遍歷網(wǎng)格，判斷網(wǎng)格路徑形成的字符串在不在Trie中拭抬，然后上下左右四個(gè)方向不斷回溯嘗試部默。
- 復(fù)雜度分析：時(shí)間復(fù)雜度
O(MN?3^L)，空間復(fù)雜度是O(max(MN, KL))造虎，visited空間是O(MN)傅蹂，字典樹O(KL)，L是最長(zhǎng)字符串的長(zhǎng)度，K是words數(shù)組的長(zhǎng)度份蝴。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 = [];
// 構(gòu)建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是為了防止重復(fù)將字符串加入到ret中
nodes[board[x][y]].isEnd = false;
}
// 處理本層狀態(tài)
nodes = nodes[board[x][y]];
str += board[x][y];
// 向四聯(lián)通方向檢索
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) {//循環(huán)word
if (!nodes[ch]) {//當(dāng)前字符不在子節(jié)點(diǎn)中 則創(chuàng)建一個(gè)子節(jié)點(diǎn)到children的響應(yīng)位置
nodes[ch] = {};
}
nodes = nodes[ch];//移動(dòng)指針到下一個(gè)字符
}
nodes.isEnd = true;//字符是否結(jié)束
};
Java:
class Solution {
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public List<String> findWords(char[][] board, String[] words) {
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
Set<String> ans = new HashSet<String>();
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<String>(ans);
}
public void dfs(char[][] board, Trie now, int i1, int j1, Set<String> 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<Character, Trie> children;
boolean isWord;
public Trie() {
this.word = "";
this.children = new HashMap<Character, Trie>();
}
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. 詞典中最長(zhǎng)的單詞 (easy)
方法1：sort+hash
- 思路：排序數(shù)組，然后遍歷字符串?dāng)?shù)組婚夫，判斷數(shù)組中的每個(gè)字符串的子串是否都在數(shù)組中
- 復(fù)雜度：時(shí)間復(fù)雜度
O(mn)浸卦，m是字符串?dāng)?shù)組的長(zhǎng)度,n是字符串最大長(zhǎng)度“覆冢空間復(fù)雜度O(m)
js：
var longestWord = function (words) {
let set = new Set()
words.forEach(v => set.add(v))//set方便查找
//先按長(zhǎng)度排序限嫌，在按字典序
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中是否有該字符串的每個(gè)子串
flag = false
break
}
}
if (flag) {
return words[i]
}
}
return ''
};
java:
class Solution {
public String longestWord(String[] words) {
Set<String> 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:字典樹
ds_160
- 思路：將所有字符串插入trie中，遞歸尋找那個(gè)長(zhǎng)度最大的單詞
- 復(fù)雜度：時(shí)間復(fù)雜度
O(mn)时捌，m是字符串?dāng)?shù)組的長(zhǎng)度,n是字符串最大長(zhǎng)度怒医。空間復(fù)雜度O(∑w)奢讨。遞歸深度不會(huì)超過(guò)最長(zhǎng)單詞長(zhǎng)度,字段書的空間復(fù)雜度是所有字符串的長(zhǎng)度和稚叹。
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) {//如果當(dāng)前字符是某一個(gè)字符串的結(jié)尾
path += key
_helper(value, path)//遞歸尋找
path = path.slice(0, -1)//回溯
}
}
}
_helper(trie.children, '')//遞歸尋找那個(gè)長(zhǎng)度最大的單詞
return res
}
var Trie = function() {
this.children = {};
};
Trie.prototype.insert = function(word) {
let nodes = this.children;
for (const ch of word) {//循環(huán)word
if (!nodes[ch]) {//當(dāng)前字符不在子節(jié)點(diǎn)中 則創(chuàng)建一個(gè)子節(jié)點(diǎn)到children的響應(yīng)位置
nodes[ch] = {};
}
nodes = nodes[ch];//移動(dòng)指針到下一個(gè)字符
}
nodes.isEnd = true;//字符是否結(jié)束
};
