數(shù)據(jù)結(jié)構(gòu)與算法之讓我們種下一棵字典樹(Java/C++雙語言實現(xiàn))-創(chuàng)新互聯(lián)
??前面的話??
本篇文章將介紹一種經(jīng)常使用的數(shù)據(jù)結(jié)構(gòu)——字典樹，它又稱Tire樹，前綴樹，字典樹，顧名思義，是關(guān)于“字典”的一棵樹。這個詞典中的每個“單詞”就是從根節(jié)點出發(fā)一直到某一個目標(biāo)節(jié)點的路徑，路徑中每條邊的字母連起來就是一個單詞，今天我們就來種下這樣的一棵樹，它在競賽和面試筆試都會經(jīng)常用到。
📒博客主頁：未見花聞的博客主頁
🎉歡迎關(guān)注🔎點贊👍收藏??留言📝
📌本文由未見花聞原創(chuàng)，首發(fā)！
📆首發(fā)時間：🌴2022年11月26日🌴
??堅持和努力一定能換來詩與遠(yuǎn)方！
💭推薦書籍：📚《無》
💬參考在線編程網(wǎng)站：🌐?？途W(wǎng)🌐力扣🌐acwing
博主的碼云gitee，平常博主寫的程序代碼都在里面。
博主的github，平常博主寫的程序代碼都在里面。
🍭作者水平很有限，如果發(fā)現(xiàn)錯誤，一定要及時告知作者哦！感謝感謝！
📌導(dǎo)航小助手📌
- 1.字典樹概述
- 1.1什么是字典樹
- 1.2字典樹的功能
- 2.字典樹的實現(xiàn)思路
- 2.1字典樹的創(chuàng)建與插入功能
- 2.2字典樹的查詢功能
- 2.3.1基本的查詢功能
- 2.3.2查詢某個字符串是否為字典樹中某一字符串的子串
- 2.3.3統(tǒng)計字典樹中每個字符串的個數(shù)
- 3.實戰(zhàn)演練：Trie字符串統(tǒng)計
- 3.1題目鏈接
- 3.2題目詳情
- 3.3解題思路
- 3.4實現(xiàn)代碼（C++/Java講解實現(xiàn)版本）
- 3.5使用數(shù)組實現(xiàn)（競賽常用）
1.字典樹概述 1.1什么是字典樹
字典樹，又被稱為Tire樹，或者稱為前綴樹，常常用于算法競賽當(dāng)中，當(dāng)然面試筆試當(dāng)中也是可能遇到的。
字典樹，顧名思義，是關(guān)于“字典”的一棵樹。即：它是對于字典的一種存儲方式（所以是一種數(shù)據(jù)結(jié)構(gòu)而不是算法）。這個詞典中的每個“單詞”就是從根節(jié)點出發(fā)一直到某一個目標(biāo)節(jié)點的路徑，路徑中每條邊的字母連起來就是一個單詞。
字典樹可以用來儲存字符串中的每個字母，并且能夠快速第查詢出來，比如有下面一組單詞：
aadb
abcd
bcgff
begin
abc將上述字符，以樹形方式存儲，結(jié)構(gòu)如下，這種結(jié)構(gòu)就是一種字典樹：
為了表示存儲在字典樹中最后一個單詞是什么，一般還會有一組配套的標(biāo)記end，表示當(dāng)前字母是否是某一個單詞的結(jié)尾，上面那一棵前綴樹根本不知道存的時候有哪些單詞存進(jìn)去了，可能字母a也存在，可能單詞ab也存在等等，所以我們需要一個結(jié)尾標(biāo)記來標(biāo)記單詞結(jié)尾的位置，于是得到了一下的字典樹。
知道了什么是字典樹，那字典樹又有什么作用呢？下面來說明一下字典樹常出現(xiàn)的情況。
根據(jù)字典樹的概念，我們可以發(fā)現(xiàn)：字典樹的本質(zhì)是把很多字符串拆成單個字符的形式，以樹的方式存儲起來。所以我們說字典樹維護(hù)的是”字典“。那么根據(jù)這個最基本的性質(zhì)，我們可以由此延伸出字典樹的很多妙用。簡單總結(jié)起來大體如下：
1、維護(hù)字符串集合（即字典）。
2、向字符串集合中插入字符串（即建樹）。
3、查詢字符串集合中是否有某個字符串（即查詢）。
4、統(tǒng)計字符串在集合中出現(xiàn)的個數(shù)（即統(tǒng)計）。
5、將字符串集合按字典序排序（即字典序排序）。
6、求集合內(nèi)兩個字符串的LCP（Longest Common Prefix，最長公共前綴）（即求最長公共前綴）。
2.字典樹的實現(xiàn)思路 2.1字典樹的創(chuàng)建與插入功能我們可以發(fā)現(xiàn)，以上列舉出的功能都是建立在“字符串集合”的基礎(chǔ)上的。再一次強(qiáng)調(diào)，字典樹是“字典”的樹，一切功能都是“字典”的功能。這也為我們使用字典樹的時候提供了一個準(zhǔn)則：看到一大堆字符串同時出現(xiàn)，就往哈希和Trie樹那邊想一下。
字典樹的插入本質(zhì)上就是通過將字符串的每個字符都存入這個“字典”上，最終所形成的一棵樹，為了表示方便，以下圖中的紅色結(jié)點表示字典樹的根結(jié)點，藍(lán)色結(jié)點表示字典樹的普通字符，綠色結(jié)點表示字典樹的結(jié)束字符，也就是原某一字符串的最后一個字符。
構(gòu)建字典樹的過程如下，字典樹的根結(jié)點一般為空，首先插入單詞aadb：
插入單詞abcd:
插入單詞bcgff：
插入單詞begin：
插入單詞abc：
上面我們從思想層面，描述了字符串插入字符到字典樹的過程，下面我們來解釋如何使用代碼實現(xiàn)上述的思路。
首先我們創(chuàng)建一個結(jié)點類，就叫做TireNode類吧，next數(shù)組表示子結(jié)點在哪里，end用來標(biāo)記是否是一個字符串的結(jié)尾字符，翻譯成代碼就是下面的這一段：
Java版本：
//實現(xiàn)class版本的前綴樹
class TireNode {public boolean end; //表示是否是結(jié)束字符
public TireNode[] next = new TireNode[26]; //表示某個字符的下一個結(jié)點的位置
//空構(gòu)造方法
public TireNode(){}
}C++版本：
class TireNode
{public:
// 記錄該字符是不是最后一個字符
bool end;
// 記錄子結(jié)點
TireNode* next[26] = {nullptr};
TireNode () {}
};其中next數(shù)組中申請了26個結(jié)點，創(chuàng)建這么多結(jié)點的意思是按照下標(biāo)號來映射某一字母，如0號下標(biāo)映射字母a，1號下標(biāo)映射字母b，以此類推，這些結(jié)點的意義是表示某字符串中一個字母的下一個字母的位置。
然后我們創(chuàng)建一個Tire類表示字典樹類，我們需要一個根結(jié)點，就叫做tire吧，也就是圖中紅色的結(jié)點，該結(jié)點只是用來指向每個字符串第一個字母的位置，因此它本身并不表示任何字符，有一個插入字符的方法，還有幾個查詢的方法。
//實現(xiàn)過程中用到的全局變量 需要放到某一個類中，博主實現(xiàn)代碼放在Main類中
class Main {//大字符串個數(shù)
private static final int N = (int) 1e5 + 2333;
//根結(jié)點
private static TireNode tire = new TireNode();
// 計數(shù)器 記錄當(dāng)前的編號
private static int idx = 0;
//層數(shù)記錄器
private static int[] cnt = new int[N];
//其他...
}
class Tire {//根結(jié)點
public TireNode tire = new TireNode();
//插入操作
public void insert() {}
//查詢操作
//返回字符串是否在字典樹內(nèi)
public boolean query(char[] cs) {}
//如果在字典樹中查詢到一個字符串返回它出現(xiàn)的次數(shù)，反之如果沒有找到返回0
public int hashQuery(char[] cs) {}
//查詢某字符串是否是字典樹某一個字符的子串
public boolean subQuery(char[] cs) {}
}C++版本：
//實現(xiàn)過程中用到的全局變量
#includeusing namespace std;
const int N = (int) 1e5 + 2333;
// 記錄每個以特定id對應(yīng)字符結(jié)尾字符串的個數(shù)
int cnt[N];
// 記錄插入字符到字典樹的實時id
int idx;
// 記錄操作的字符串
char str[N];
class Tire
{public:
TireNode* tire = new TireNode();
void insert() {}
boolean query(char* cs) {}
int hashQuery(char* cs) {}
boolean subQuery(char* cs) {}
} 插入操作的思路就是，遍歷傳入字符串中的每一個字符，并同步遍歷字典樹結(jié)點cur，從根節(jié)點開始，找到該字符映射在next數(shù)組的位置u，如果發(fā)現(xiàn)對應(yīng)位置為空，表示這個字符還沒有被插入到字典樹，我們就新建一個結(jié)點，并賦值給next[u]，賦值完成后，并將cur更新為該新結(jié)點next[u]，直到字符串遍歷完成為止，遍歷完后，我們將最后一個字符對應(yīng)的TireNode對象的end標(biāo)記為true，表示該字符是結(jié)尾字符，實現(xiàn)代碼如下：
Java版本：
//插入操作
private static void insert(char[] cs) {TireNode cur = tire;
int p = 0;
for (int i = 0; i< cs.length; i++) {int u = cs[i] - 'a';
if (cur.next[u] == null) cur.next[u] = new TireNode();
cur = cur.next[u];
}
//將最后一個字符做上end標(biāo)記
cur.end = true;
}C++版本：
//插入操作
void insert(char* cs)
{TireNode* cur = tire;
for (int i = 0; cs[i] != '\0'; i++)
{int u = cs[i] - 'a';
//cout<< u<< endl;
if (cur->next[u] == nullptr) cur->next[u] = new TireNode();
cur = cur->next[u];
}
cur->end = true;
}字典樹查詢操作其實和插入操作大同小異，遍歷的方式與插入一模一樣，只不過如果遇到某字符對應(yīng)的next數(shù)組元素為空，表示該字典樹不包含該字符串，直接返回false，就是相當(dāng)于字典樹里面存了ab，查詢字符串為abc，字符串遍歷到c時，對應(yīng)位置next數(shù)組元素為空。
遍歷完所有查詢字符串，所有字符都能在next數(shù)組中匹配上，此時能說明一定含有該字符嗎？對于這個問題，我們來舉一個栗子，字典樹里面存了字符串abc，查詢字符串為ab，很明顯可以順利遍歷完查詢字符串，但是字符串ab并不在字典樹當(dāng)中，所以說就算所有的字符與next數(shù)組匹配，但是并一定就在字典樹內(nèi)，此時end標(biāo)記的作用就出來了，我們只需判斷查詢字符串的最后一個字符是否是字典樹中某一個字符串的最后一個字符就可以了，就比如上面的例子，查詢字符串的最后一個字符b，在字典樹當(dāng)中并不是最后一個字符，所以返回false，如果是最后一個字符，那就返回true，根據(jù)這個思路我們可以寫出代碼：
Java代碼實現(xiàn)：
//查詢操作 返回是否存在
private static boolean query(char[] cs) {TireNode cur = tire;
for (int i = 0; i< cs.length; i++) {int u = cs[i] - 'a';
if (cur.next[u] == null) return false;
cur = cur.next[u];
}
return cur.end;
}C++代碼實現(xiàn)：
//查詢操作
bool query(char* cs)
{TireNode* cur = tire;
for (int i = 0; cs[i] != '\0'; i++)
{int u = cs[i] - 'a';
if (cur->next[u] == nullptr) return false;
cur = cur->next[u];
}
if (!cur->end) return false;
return true;
}查詢一個字符串是否是另外一個字符串的子串，與普通匹配查詢是一樣的，只不過最后不需要進(jìn)行end標(biāo)記的判斷，因為要查詢字符串中的字符位置都在字典樹中一一匹配，那么該查詢字符串那肯定就是字典樹中某一個字符串的子串了，實現(xiàn)代碼：
Java版本代碼：
//查詢操作 返回是否存在子串
private static boolean query(char[] cs) {TireNode cur = tire;
for (int i = 0; i< cs.length; i++) {int u = cs[i] - 'a';
if (cur.next[u] == null) return false;
cur = cur.next[u];
}
return true;
}C++版本代碼：
//查詢操作
bool subQuery(char* cs)
{TireNode* cur = tire;
for (int i = 0; cs[i] != '\0'; i++)
{int u = cs[i] - 'a';
if (cur->next[u] == nullptr) return false;
cur = cur->next[u];
}
return true;
}對于這個問題，其實思路有很多種，你可以搭配一個哈希表來對字符串個數(shù)進(jìn)行計數(shù)，也可以通過對字典樹中的每一個字符進(jìn)行編號，首先我們需要知道，在字典樹中作為結(jié)尾字符的結(jié)點對應(yīng)的字符串是唯一的，因為字符串插入到字典樹后，從根節(jié)點到字符串最后一個字符對應(yīng)字符的路徑是唯一的也是確認(rèn)的，如果另外一個字符串路徑與該字符串相同，那么另外一個字符串的結(jié)尾字符落在的字典樹的位置一定與原字符相同，對于該字符串的子串或者作為另外一個字符串的子串，其在字典樹上的路徑會出現(xiàn)重合，但是結(jié)尾字符所對應(yīng)字典樹的位置一定是不相同的。
比如字符串abc與abcd，雖然前面三個字符位置是一模一樣的，但是結(jié)束位置是不相同的，如果相同，那一定就是相同的字符串。
根據(jù)這個性質(zhì)，我們可以在插入的時候，將所有的字符都標(biāo)上一個唯一的編號，然后我們以結(jié)束位置結(jié)點的編號為基準(zhǔn)，創(chuàng)建一個數(shù)組，將編號映射到數(shù)組下標(biāo)并進(jìn)行計數(shù)，畢竟一個字符串對應(yīng)結(jié)束位置是唯一的，那么自然編號也是唯一的，那么就可以間接地通過編號來代表字符串進(jìn)行計數(shù)。
因為計數(shù)是在字典樹創(chuàng)建或插入的時候完成的，所以查詢的時候我們可以通過所給字符串找到字符串的結(jié)尾位置的編號，來獲取對應(yīng)字符串在字典樹中出現(xiàn)的次數(shù)。
為了編號方便，我們可以在節(jié)點類中加上一個屬性id，表示當(dāng)前結(jié)點的編號：
Java:
class TireNode {public boolean end; //表示是否是結(jié)束字符
public TireNode[] next = new TireNode[26]; //表示某個字符的下一個結(jié)點的位置
public int id; //表示該字符在字典樹中的編號
//空構(gòu)造方法
public TireNode(){}
//初始化id構(gòu)造
public TireNode (int id) {this.id = id;
}
}C++:
class TireNode
{public:
// 記錄該字符是不是最后一個字符
bool end;
// 記錄子結(jié)點
TireNode* next[26] = {nullptr};
// 記錄以該字符結(jié)尾的id
int id;
TireNode () {}
TireNode(int _id) {id = _id;
}
};將計數(shù)操作嵌入到插入操作的實現(xiàn)代碼如下：
Java實現(xiàn)代碼：
//其中idx為全局變量，作用是遞增生成編號，為插入時的每一個節(jié)點編號
//插入操作
private static void insert(char[] cs) {TireNode cur = tire;
int p = 0;
for (int i = 0; i< cs.length; i++) {int u = cs[i] - 'a';
if (cur.next[u] == null) cur.next[u] = new TireNode(++idx);
cur = cur.next[u];
}
//將最后一個字符做上end標(biāo)記
cur.end = true;
// 對以該字符結(jié)尾的字符串進(jìn)行計數(shù)
cnt[cur.id]++;
}C++實現(xiàn)代碼：
//其中idx為全局變量，作用是遞增生成編號，為插入時的每一個節(jié)點編號
//cpp實現(xiàn)過程中，將字符串輸入到了一個足夠大的char數(shù)組當(dāng)中，所以可以使用判斷\0來判斷結(jié)尾
//cpp使用string就可以做到與java一模一樣了
//插入操作
void insert(char* cs)
{TireNode* cur = tire;
for (int i = 0; cs[i] != '\0'; i++)
{int u = cs[i] - 'a';
//cout<< u<< endl;
if (cur->next[u] == nullptr) cur->next[u] = new TireNode(++idx);
cur = cur->next[u];
}
cur->end = true;
//計數(shù)
cnt[cur->id]++;
}查詢操作也是一樣的，只不過把返回值改為結(jié)尾位置編號對應(yīng)的計數(shù)數(shù)組中的計數(shù)次數(shù)，實現(xiàn)代碼：
Java版本：
// 查詢操作 返回查詢到字符串當(dāng)前的個數(shù)
private static int hashQuery(char[] cs) {TireNode cur = tire;
for (int i = 0; i< cs.length; i++) {int u = cs[i] - 'a';
if (cur.next[u] == null) return 0;
cur = cur.next[u];
}
if (cur.end) return cnt[cur.id];
return 0;
}C++版本：
//查詢操作
int hashQuery(char* cs)
{TireNode* cur = tire;
for (int i = 0; cs[i] != '\0'; i++)
{int u = cs[i] - 'a';
if (cur->next[u] == nullptr) return 0;
cur = cur->next[u];
}
if (!cur->end) return 0;
return cnt[cur->id];
}835. Trie字符串統(tǒng)計
3.2題目詳情維護(hù)一個字符串集合，支持兩種操作：
I x 向集合中插入一個字符串 x；
Q x 詢問一個字符串在集合中出現(xiàn)了多少次。
共有 N 個操作，所有輸入的字符串總長度不超過
1
0
5
10^5
105，字符串僅包含小寫英文字母。
輸入格式
第一行包含整數(shù) N，表示操作數(shù)。
接下來 N 行，每行包含一個操作指令，指令為 I x 或 Q x 中的一種。
輸出格式
對于每個詢問指令 Q x，都要輸出一個整數(shù)作為結(jié)果，表示 x 在集合中出現(xiàn)的次數(shù)。
每個結(jié)果占一行。
數(shù)據(jù)范圍
1
≤
N
≤
2
?
1
0
4
1≤N≤2?10^4
1≤N≤2?104
輸入樣例：
5
I abc
Q abc
Q ab
I ab
Q ab輸出樣例：
1
0
1其實就是對我們上面所講的字典樹各個操作的綜合題而已，思路就不多提了，不過在競賽當(dāng)中，用的更多的是使用數(shù)組實現(xiàn)字典樹，僅僅就是將class實現(xiàn)的方式改為使用純數(shù)組實現(xiàn)罷了，思路是一模一樣的，我就不具體細(xì)說數(shù)組版本實現(xiàn)的細(xì)節(jié)了，后面會給出該題數(shù)組版本的實現(xiàn)代碼。
Java代碼實現(xiàn)：
import java.util.*;
//實現(xiàn)class版本的前綴樹
class TireNode {public boolean end; //表示是否是結(jié)束字符
public TireNode[] next = new TireNode[26]; //表示某個字符的下一個結(jié)點的位置
public int id; //表示該字符在字典樹中的編號
//空構(gòu)造方法
public TireNode(){}
//初始化id構(gòu)造
public TireNode (int id) {this.id = id;
}
}
class Main {//大字符串個數(shù)
private static final int N = (int) 1e5 + 2333;
//根結(jié)點
private static TireNode tire = new TireNode();
// 計數(shù)器 記錄當(dāng)前的編號
private static int idx = 0;
//層數(shù)記錄器
private static int[] cnt = new int[N];
//插入操作
private static void insert(char[] cs) {TireNode cur = tire;
int p = 0;
for (int i = 0; i< cs.length; i++) {int u = cs[i] - 'a';
if (cur.next[u] == null) cur.next[u] = new TireNode(++idx);
cur = cur.next[u];
}
//將最后一個字符做上end標(biāo)記
cur.end = true;
// 對以該字符結(jié)尾的字符串進(jìn)行計數(shù)
cnt[cur.id]++;
}
// 查詢操作 返回查詢到字符串當(dāng)前的個數(shù)
private static int hashQuery(char[] cs) {TireNode cur = tire;
for (int i = 0; i< cs.length; i++) {int u = cs[i] - 'a';
if (cur.next[u] == null) return 0;
cur = cur.next[u];
}
if (cur.end) return cnt[cur.id];
return 0;
}
public static void main(String[] args) {Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();
while (n-- >0) {String s = sc.nextLine();
String[] ss = s.split(" ");
char op = ss[0].charAt(0);
String str = ss[1];
char[] cs = str.toCharArray();
if (op == 'I') insert(cs);
else if (op == 'Q') System.out.println(hashQuery(cs));
}
}
}C++代碼實現(xiàn)：
#includeusing namespace std;
const int N = (int) 1e5 + 2333;
// 記錄每個以特定id對應(yīng)字符結(jié)尾字符串的個數(shù)
int cnt[N];
// 記錄插入字符到字典樹的實時id
int idx;
// 記錄操作的字符串
char str[N];
class TireNode
{public:
// 記錄該字符是不是最后一個字符
bool end;
// 記錄子結(jié)點
TireNode* next[26] = {nullptr};
// 記錄以該字符結(jié)尾的id
int id;
TireNode () {}
TireNode(int _id) {id = _id;
}
};
class Tire
{public:
//根結(jié)點
TireNode* tire = new TireNode();
//插入操作
void insert(char* cs)
{TireNode* cur = tire;
for (int i = 0; cs[i] != '\0'; i++)
{int u = cs[i] - 'a';
//cout<< u<< endl;
if (cur->next[u] == nullptr) cur->next[u] = new TireNode(++idx);
cur = cur->next[u];
}
cur->end = true;
cnt[cur->id]++;
}
//查詢操作
int hashQuery(char* cs)
{TireNode* cur = tire;
for (int i = 0; cs[i] != '\0'; i++)
{int u = cs[i] - 'a';
if (cur->next[u] == nullptr) return 0;
cur = cur->next[u];
}
if (!cur->end) return 0;
return cnt[cur->id];
}
};
int main()
{int n;
cin >>n;
Tire tireTree;
while (n-- >0)
{char op[2];
cin >>op >>str;
if (op[0] == 'I') tireTree.insert(str);
else if (op[0] == 'Q') cout<< tireTree.hashQuery(str)<< endl;
}
return 0;
} 簡單的說一下吧，N為字符串的所有輸入字符串的大長度，所以字典樹的結(jié)點個數(shù)大為N，那么最多可能也就是有N個next數(shù)組，代碼中nes二維數(shù)組表示對應(yīng)著前面的next數(shù)組，只不過把所有的結(jié)點的next數(shù)組都集中在一起罷了，所以我們也可以使用編號為每一個結(jié)點分配next數(shù)組，剩余的idx等變量含義與上面以class方式實現(xiàn)代碼中的意思是一樣的。
Java代碼：
import java.util.*;
class Main {private static final int N = (int) 1e5 + 2333;
private static int[][] nes = new int[N][26];
private static int[] cnt = new int[N];
private static int idx;
//插入操作
private static void insert(char[] cs) {int p = 0;
for (int i = 0; i< cs.length; i++) {int u = cs[i] - 'a';
if (nes[p][u] == 0) nes[p][u] = ++idx;
//更新p
p = nes[p][u];
}
//對應(yīng)字符串?dāng)?shù)量加1
cnt[p]++;
}
//查詢操作
private static int query(char[] cs) {int p = 0;
for (int i = 0; i< cs.length; i++) {int u = cs[i] - 'a';
if (nes[p][u] == 0) return 0; //代表沒有找到，找到的字符串?dāng)?shù)量為0
//更新p
p = nes[p][u];
}
//找到了返回該字符串的數(shù)量
return cnt[p];
}
public static void main(String[] args) {Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();
while (n-- >0) {String s = sc.nextLine();
String[] ss = s.split(" ");
char op = ss[0].charAt(0);
String str = ss[1];
char[] cs = str.toCharArray();
if (op == 'I') insert(cs);
else if (op == 'Q') System.out.println(query(cs));
}
}
}C++實現(xiàn)版本：
#includeusing namespace std;
const int N = (int) 1e5 + 2333;
//使用純數(shù)組實現(xiàn)
int idx; //表示結(jié)點的編號
int nes[N][26]; //表示某個字母的next數(shù)組 記錄該字母所在字符串下一個字符的編號，為0表示該字母為結(jié)束字母
int cnt[N]; //記錄在nes[p][u]位置結(jié)尾字符的字符串?dāng)?shù)量（也就是某一個字符串插入在字典樹的數(shù)量）
char str[N]; //記錄需要插入或者查詢的字符串
//插入字符串
void insert(char* str)
{int p = 0;
for (int i = 0; str[i] != 0; i++)
{//如果遇到\0表示字符已經(jīng)結(jié)束了
//獲取字符在字母表的順序
int u = str[i] - 'a';
if (nes[p][u] == 0) nes[p][u] = ++idx;
//更新p
p = nes[p][u];
}
//將當(dāng)前字符串?dāng)?shù)量++
cnt[p]++;
}
//查詢字符串是否存在
int query(char* str)
{int p = 0;
for (int i = 0; str[i] != 0; i++)
{int u = str[i] - 'a';
if (nes[p][u] == 0) return 0; //即返回false的意思
p = nes[p][u];
}
return cnt[p];
}
int main()
{int n;
cin >>n;
while (n-- >0)
{char op[2];
cin >>op >>str;
if (op[0] == 'I') insert(str);
else if (op[0] == 'Q') cout<< query(str)<< endl;
}
return 0;
} 參考資料：
字典樹(Trie)詳解
力扣中的字典樹：
劍指 Offer II 062. 實現(xiàn)前綴樹
208. 實現(xiàn) Trie (前綴樹)
472. 連接詞
676. 實現(xiàn)一個魔法字典
648. 單詞替換
745. 前綴和后綴搜索
820. 單詞的壓縮編碼
面試題 17.13. 恢復(fù)空格
劍指 Offer II 064. 神奇的字典
劍指 Offer II 063. 替換單詞
劍指 Offer II 065. 最短的單詞編碼
2416. 字符串的前綴分?jǐn)?shù)和
0-1字典樹（傳統(tǒng)字典樹變形）
劍指 Offer II 067. 大的異或
1707. 與數(shù)組中元素的大異或值
哈希表+字典樹
面試題 16.02. 單詞頻率
劍指 Offer II 066. 單詞之和
劍指 Offer II 063. 替換單詞
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
網(wǎng)頁名稱：數(shù)據(jù)結(jié)構(gòu)與算法之讓我們種下一棵字典樹(Java/C++雙語言實現(xiàn))-創(chuàng)新互聯(lián)
分享鏈接：http://m.jiaotiyi.com/article/pphgh.html