1.什么是前缀树
前缀树是N叉树的一种特殊形式。通常来说，一个前缀树是用来存储字符串的。前缀树的每一个节点代表一个字符串（前缀）。每一个节点会有多个子节点，通往不同子节点的路径上有着不同的字符。子节点代表的字符串是由节点本身的原始字符串，以及通往该子节点路径上所有的字符组成的。
下面是前缀树的一个例子
image.png
在上图示例中，我们在节点中标记的值是该节点对应表示的字符串。例如，我们从根节点开始，选择第二条路径 'b'，然后选择它的第一个子节点 'a'，接下来继续选择子节点 'd'，我们最终会到达叶节点 "bad"。节点的值是由从根节点开始，与其经过的路径中的字符按顺序形成的。
值得注意的是，根节点表示空字符串。
前缀树的一个重要的特性是，节点所有的后代都与该节点相关的字符串有着共同的前缀。这就是前缀树名称的由来。
我们再来看这个例子。例如，以节点 "b" 为根的子树中的节点表示的字符串，都具有共同的前缀 "b"。反之亦然，具有公共前缀 "b" 的字符串，全部位于以 "b" 为根的子树中，并且具有不同前缀的字符串来自不同的分支。
前缀树有着广泛的应用，例如自动补全，拼写检查等等。我们将在后面的章节中介绍实际应用场景。
2 如何表示一个前缀树？
前缀树的特别之处在于字符和子节点之间的对应关系。有许多不同的表示前缀树节点的方法，这里我们只介绍其中的两种方法。
2.1 数组
第一种方法是用数组存储子节点。
例如，如果我们只存储含有字母 a 到 z 的字符串，我们可以在每个节点中声明一个大小为26的数组来存储其子节点。对于特定字符 c，我们可以使用 c - 'a' 作为索引来查找数组中相应的子节点。
// 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']
*/
访问子节点十分快捷。访问一个特定的子节点比较容易，因为在大多数情况下，我们很容易将一个字符转换为索引。但并非所有的子节点都需要这样的操作，所以这可能会导致空间的浪费。
#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 来存储子节点。
我们可以在每个节点中声明一个Hashmap。Hashmap的键是字符，值是相对应的子节点。
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]
*/
通过相应的字符来访问特定的子节点更为容易。但它可能比使用数组稍慢一些。但是，由于我们只存储我们需要的子节点，因此节省了空间。这个方法也更加灵活，因为我们不受到固定长度和固定范围的限制。
我们已经提到过如何表示前缀树中的子节点。除此之外，我们也需要用到一些其他的值。
例如，我们知道，前缀树的每个节点表示一个字符串，但并不是所有由前缀树表示的字符串都是有意义的。如果我们只想在前缀树中存储单词，那么我们可能需要在每个节点中声明一个布尔值（Boolean）作为标志，来表明该节点所表示的字符串是否为一个单词。
3 leetcode题目最长公共前缀
思路非常简单，由于是寻找最长前缀，所以只需要插入第一个字符串，后续字符串分别进行匹配即可，更优化一点可以先遍历字符数组，找到最短的那个字符串，再进行匹配。
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;
}
};
网友评论