基础
{“a”,“abc”,“bac”,“bbc”,“ca” }的字典树如下图：
最主用的应用：一，字符串编码。二，位运算。
字符串编码
相比利用哈希映射编码，优点如下：
依次查询长度为n的字符串s的前缀时间复杂度是O(n)。查询完s[0…i]，再查询s[0…i+1]的时间复杂度是O(1)。而哈希映射的时间复杂度是：O(nn)。
利用哈希映射编码的代码如下：
注意m_iLeafIndex 为-1，表示此节点不是任何字符串的结束字符。
class CStrToIndex
{
public:
CStrToIndex() {
}
CStrToIndex(const vector<string>& wordList) {
for (const auto& str : wordList)
{
Add(str);
}
}
int Add(const string& str)
{
if (m_mIndexs.count(str)) { return m_mIndexs[str]; }
m_mIndexs[str] = m_strs.size();
m_strs.push_back(str);
return m_strs.size()-1;
}
vector<string> m_strs;
int GetIndex(const string& str)
{
if (m_mIndexs.count(str)) { return m_mIndexs[str]; }
return -1;
}
protected:
unordered_map<string, int> m_mIndexs;
};
利用字典树编码的代码如下：
template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrieNode
{
public:
~CTrieNode()
{
for (auto& [tmp, ptr] : m_dataToChilds) {
delete ptr;
}
}
CTrieNode* AddChar(TData ele, int& iMaxID)
{
#ifdef _DEBUG
if ((ele < cBegin) || (ele >= cBegin + iTypeNum))
{
return nullptr;
}
#endif
const int index = ele - cBegin;
auto ptr = m_dataToChilds[ele - cBegin];
if (!ptr)
{
m_dataToChilds[index] = new CTrieNode();
#ifdef _DEBUG
m_dataToChilds[index]->m_iID = ++iMaxID;
m_childForDebug[ele] = m_dataToChilds[index];
#endif
}
return m_dataToChilds[index];
}
CTrieNode* GetChild(TData ele)
{
#ifdef _DEBUG
if ((ele < cBegin) || (ele >= cBegin + iTypeNum))
{
return nullptr;
}
#endif
return m_dataToChilds[ele - cBegin];
}
protected:
#ifdef _DEBUG
int m_iID = -1;
std::unordered_map<TData, CTrieNode*> m_childForDebug;
#endif
public:
int m_iLeafIndex = -1;
protected:
//CTrieNode* m_dataToChilds[iTypeNum] = { nullptr };//空间换时间 大约216字节
//unordered_map<int, CTrieNode*> m_dataToChilds;//时间换空间 大约56字节
map<int, CTrieNode*> m_dataToChilds;//时间换空间,空间略优于哈希映射，数量小于256时，时间也优。大约48字节
};
template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrie
{
public:
int GetLeadCount()
{
return m_iLeafCount;
}
CTrieNode<TData, iTypeNum, cBegin>* AddA(CTrieNode<TData, iTypeNum, cBegin>* par,TData curValue)
{
auto curNode =par->AddChar(curValue, m_iMaxID);
FreshLeafIndex(curNode);
return curNode;
}
template<class IT>
int Add(IT begin, IT end)
{
auto pNode = &m_root;
for (; begin != end; ++begin)
{
pNode = pNode->AddChar(*begin, m_iMaxID);
}
FreshLeafIndex(pNode);
return pNode->m_iLeafIndex;
}
template<class IT>
CTrieNode<TData, iTypeNum, cBegin>* Search(IT begin, IT end)
{
auto ptr = &m_root;
for (; begin != end; ++begin)
{
ptr = ptr->GetChild(*begin);
if (nullptr == ptr)
{
return nullptr;
}
}
return ptr;
}
CTrieNode<TData, iTypeNum, cBegin> m_root;
protected:
void FreshLeafIndex(CTrieNode<TData, iTypeNum, cBegin>* pNode)
{
if (-1 == pNode->m_iLeafIndex)
{
pNode->m_iLeafIndex = m_iLeafCount++;
}
}
int m_iMaxID = 0;
int m_iLeafCount = 0;
};
二进制位运算（01前缀树)
比如求nums和x的xor最大值。
将nums放到01放到前缀树中。通过拆位法依次从高到低处理各位，如果x 此为1，则优先选择前缀树的0分支；如果x为0，则优先选择前缀树的1分支。
class C2BNumTrieNode
{
public:
C2BNumTrieNode()
{
m_childs[0] = m_childs[1] = nullptr;
}
bool GetNot0Child(bool bFirstRight)
{
auto ptr = m_childs[bFirstRight];
if (ptr && (ptr->m_iNum > 0))
{
return bFirstRight;
}
return !bFirstRight;
}
int m_iNum = 0;
C2BNumTrieNode* m_childs[2];
};
template<class T = int, int iLeveCount = 31>
class C2BNumTrie
{
public:
C2BNumTrie()
{
m_pRoot = new C2BNumTrieNode();
}
void Add(T iNum)
{
m_setHas.emplace(iNum);
C2BNumTrieNode* p = m_pRoot;
for (int i = iLeveCount - 1; i >= 0; i--)
{
p->m_iNum++;
bool bRight = iNum & ((T)1 << i);
if (nullptr == p->m_childs[bRight])
{
p->m_childs[bRight] = new C2BNumTrieNode();
}
p = p->m_childs[bRight];
}
p->m_iNum++;
}
void Del(T iNum)
{
auto it = m_setHas.find(iNum);
if (m_setHas.end() == it)
{
return;
}
m_setHas.erase(it);
C2BNumTrieNode* p = m_pRoot;
for (int i = iLeveCount - 1; i >= 0; i--)
{
p->m_iNum--;
bool bRight = iNum & ((T)1 << i);
p = p->m_childs[bRight];
}
p->m_iNum--;
}
void Swap(C2BNumTrie<T, iLeveCount>& o) {
swap(m_pRoot, o.m_pRoot);
swap(m_setHas, o.m_setHas);
}
C2BNumTrieNode* m_pRoot;
std::unordered_multiset<T> m_setHas;
};
template<class T = int, int iLeveCount = 31>
class CMaxXor2BTrie : public C2BNumTrie<T, iLeveCount>
{
public:
T MaxXor(T iNum)
{
C2BNumTrieNode* p = C2BNumTrie<T, iLeveCount>::m_pRoot;
T iRet = 0;
for (int i = iLeveCount - 1; i >= 0; i--)
{
bool bRight = !(iNum & ((T)1 << i));
bool bSel = p->GetNot0Child(bRight);
p = p->m_childs[bSel];
if (bSel == bRight)
{
iRet |= ((T)1 << i);
}
}
return iRet;
}
};
题解
| 给字符串编码 | 难道分 |
|---|---|
| 字典树】 【哈希表】 【字符串】3076. 数组中的最短非公共子字符串 | 1635 |
| 【字典树（前缀树) 字符串】2416. 字符串的前缀分数和需要记录子孙数量 | 1725 |
| 【字典树 最长公共前缀】1316. 不同的循环子字符串 | 1836 |
| 【字典树（前缀树）】1032. 字符流 | 1970 |
| 【map】【滑动窗口】【字典树】C++算法：2781最长合法子字符串的长度 | 2203 |
| 【字典树】【字符串】【 前缀】3093. 最长公共后缀查询 | 2118 |
| 【字典树】【KMP】【C++算法】3045统计前后缀下标对 II | 2327 |
| 【字典树 离线查询 深度优先】1938. 查询最大基因差 | 2502 |
| 动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本 | 2695 |
| 【动态规划】 【字典树】C++算法：472 连接词 | |
| 【回溯 字典树（前缀树）】212. 单词搜索 II | |
| 【字典树 马拉车算法】336. 回文对 |
| 01前缀树 | |
|---|---|
| 【字典树】2935找出强数对的最大异或值 II | 2348 |
| 【字典树（前缀树） 异或 离线查询】1707. 与数组中元素的最大异或值 | 2358 |
| 【字典树（前缀树） 位运算】1803. 统计异或值在范围内的数对有多少 | 2479 |
| 其它前缀树 | |
|---|---|
| 【字典树（前缀树) 哈希映射 后序序列化】1948. 删除系统中的重复文件夹需要DFS | 2533 |
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 《喜缺全书算法册》以原理、正确性证明、总结为主。 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
![【Qt秘籍】[010]-Qt常用控件](https://img-blog.csdnimg.cn/direct/609be2c4190f453abf8ed2ec47efa38e.png)
