1.什么是前綴樹
前綴樹是N叉樹的一種特殊形式。通常來說，一個前綴樹是用來存儲字符串的。前綴樹的每一個節(jié)點代表一個字符串（前綴）。每一個節(jié)點會有多個子節(jié)點，通往不同子節(jié)點的路徑上有著不同的字符。子節(jié)點代表的字符串是由節(jié)點本身的原始字符串，以及通往該子節(jié)點路徑上所有的字符組成的。
下面是前綴樹的一個例子
在上圖示例中，我們在節(jié)點中標記的值是該節(jié)點對應表示的字符串。例如，我們從根節(jié)點開始，選擇第二條路徑 'b'，然后選擇它的第一個子節(jié)點 'a'，接下來繼續(xù)選擇子節(jié)點 'd'，我們最終會到達葉節(jié)點 "bad"。節(jié)點的值是由從根節(jié)點開始，與其經(jīng)過的路徑中的字符按順序形成的。
值得注意的是，根節(jié)點表示空字符串。
前綴樹的一個重要的特性是，節(jié)點所有的后代都與該節(jié)點相關的字符串有著共同的前綴。這就是前綴樹名稱的由來。
我們再來看這個例子。例如，以節(jié)點 "b" 為根的子樹中的節(jié)點表示的字符串，都具有共同的前綴 "b"。反之亦然，具有公共前綴 "b" 的字符串，全部位于以 "b" 為根的子樹中，并且具有不同前綴的字符串來自不同的分支。
前綴樹有著廣泛的應用，例如自動補全，拼寫檢查等等。我們將在后面的章節(jié)中介紹實際應用場景。
2 如何表示一個前綴樹？
前綴樹的特別之處在于字符和子節(jié)點之間的對應關系。有許多不同的表示前綴樹節(jié)點的方法，這里我們只介紹其中的兩種方法。
2.1 數(shù)組
第一種方法是用數(shù)組存儲子節(jié)點。
例如，如果我們只存儲含有字母 a 到 z 的字符串，我們可以在每個節(jié)點中聲明一個大小為26的數(shù)組來存儲其子節(jié)點。對于特定字符 c，我們可以使用 c - 'a' 作為索引來查找數(shù)組中相應的子節(jié)點。
// change this value to adapt to different cases
#define N 26
struct TrieNode {
TrieNode* children[N];
// you might need some extra values according to different cases
};
/** Usage:
* Initialization: TrieNode root = new TrieNode();
* Return a specific child node with char c: (root->children)[c - 'a']
*/
訪問子節(jié)點十分快捷。訪問一個特定的子節(jié)點比較容易，因為在大多數(shù)情況下，我們很容易將一個字符轉換為索引。但并非所有的子節(jié)點都需要這樣的操作，所以這可能會導致空間的浪費。
#include <iostream>
#include <map>
#include <vector>
#define N 26
using namespace std;
class Trie{
private:
struct Node{
Node* next[N];
bool is_w = false;//是否是一個完整的單詞
};
Node* trie;
public:
Trie(){
trie = new Node();
}
/*insert word*/
void insert(const string & str){
Node* cur = trie;
for(int i = 0;i < str.size();i++){
if(cur->next[str[i] - 'a'] == nullptr)
cur->next[str[i] - 'a']= new Node();
cur = cur->next[str[i] - 'a'];
}
cur->is_w = true;
}
bool search(const string & str) {
Node* cur = trie;
for(int i = 0;i < str.size();i++){
if(cur->next[str[i] - 'a'] != nullptr)
cur = cur->next[str[i] - 'a'];
else
return false;
}
if(cur->is_w) return true;
else return false;
}
};
int main(){
Trie t;
t.insert("apple");
t.insert("banana");
cout << t.search("apple") << endl;
cout << t.search("banana") << endl;
return 0;
}
2.2 Map
第二種方法是使用 Hashmap 來存儲子節(jié)點。
我們可以在每個節(jié)點中聲明一個Hashmap。Hashmap的鍵是字符，值是相對應的子節(jié)點。
struct TrieNode {
unordered_map<char, TrieNode*> children;
// you might need some extra values according to different cases
};
/** Usage:
* Initialization: TrieNode root = new TrieNode();
* Return a specific child node with char c: (root->children)[c]
*/
通過相應的字符來訪問特定的子節(jié)點更為容易。但它可能比使用數(shù)組稍慢一些。但是，由于我們只存儲我們需要的子節(jié)點，因此節(jié)省了空間。這個方法也更加靈活，因為我們不受到固定長度和固定范圍的限制。
我們已經(jīng)提到過如何表示前綴樹中的子節(jié)點。除此之外，我們也需要用到一些其他的值。
例如，我們知道，前綴樹的每個節(jié)點表示一個字符串，但并不是所有由前綴樹表示的字符串都是有意義的。如果我們只想在前綴樹中存儲單詞，那么我們可能需要在每個節(jié)點中聲明一個布爾值（Boolean）作為標志，來表明該節(jié)點所表示的字符串是否為一個單詞。
3 leetcode題目最長公共前綴
思路非常簡單，由于是尋找最長前綴，所以只需要插入第一個字符串，后續(xù)字符串分別進行匹配即可，更優(yōu)化一點可以先遍歷字符數(shù)組，找到最短的那個字符串，再進行匹配。
class Solution {
public:
struct Node{
Node* next[26];
bool isStr;
};
void insertTrie(Node* root,const string &str){
if(root == nullptr) return;
for(int i = 0;i < str.size();i++){
if(root->next[str[i] - 'a'] == nullptr){
root->next[str[i] - 'a'] = new Node();
}
root = root->next[str[i] - 'a'];
}
root->isStr = true;
}
int searchCommonPrefix(Node* root, const string& str){
if(root == nullptr) return 0;
int maxCommon = 0;
for(int i = 0;i < str.size();i++){
if(root->next[str[i] - 'a'] == nullptr)
return maxCommon;
else{
maxCommon++;
root = root->next[str[i] - 'a'];
}
}
return maxCommon;
}
string longestCommonPrefix(vector<string>& strs) {
string result = "";
if(strs.size() == 0) return result;
if(strs.size() == 1) return strs[0];
Node* trie = new Node();
insertTrie(trie,strs[0]);
int maxCommon = strs[0].size();
for (int i = 1;i < strs.size();i++){
maxCommon = maxCommon > searchCommonPrefix(trie,strs[i]) ? searchCommonPrefix(trie,strs[i]) : maxCommon;
if(maxCommon == 0) return result;
}
for(int i = 0;i <maxCommon;i++){
result += strs[0][i];
}
return result;
}
};
