抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

字典树

misaka10032

发布于：Mar 9, 2021
次浏览

test
字典树，即Trie树，是一种哈希树的变种的树形结构。利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
字典树本身具有如下的几点性质：
·根节点不包含字符，除根节点外的每一个子节点都包含一个字符
·从根节点到某一节点。路径上经过的字符连接起来，就是该节点对应的字符串
·每个节点的所有子节点包含的字符都不相同
一颗字典树的样子如下图所示：
test1
通常字典树的查询时间复杂度是O(logL)，其中L是字符串的长度。通常建立的字典树是一颗26叉树，其实也就是包含了所有小写字母在内，对于可能包含其他字符的情况，可以通过增加孩子节点数目来对字典树能够处理的范围进行扩容。虽然字典树是一颗多叉树，但这种数据结构所涉及的操作相对简单，因此构建一颗字典树所需要的代码难度相对较小。ps.trie是AC自动机的一部分。虽然还不太了解什么是AC自动机雾
以下便是字典树的模板实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
truct node
{
   struct node *next[26];  //孩子节点
   int num;  //孩子节点的数目
};
node *creat()  //新建一颗字典树
{
   node *p=new node;
   for(int i=0;i<26;i++)
   {
       p->next[i]=NULL;
   }
   p->num=0;
   return p;
}
void insert(string s,node *head)
{
    int len=s.length();
    node *t=head;
    node *p=head;
    for(int i=0;i<len;i++)
    {
        int c=s[i]-'a';
        if(p->nect[c]==NULL)
        {
            t=creat();
            p->next[c]=t;
            p->num++;
            p=p->next[c];
        }
        else 
        {
            p=p->next[c];
        }
    }
}
int search(string s,node *head)
{
    node *p=head;
    int len=s.length();
    for(int i=0;i<len;i++)
    {
        int c=s[i]-'a';
        if(p->next[c]==NULL)
        {
            return 0;
        }
    }
    else
    {
        p=p->next[c];
    }
}

字典树就如同他的名字一样，如同字典般的结构，对于需要多次查询和包含前缀的问题的高效解决有着十足的优势。具体的使用示例便以LeetCode的1268题为例。[https://leetcode-cn.com/problems/search-suggestions-system/]
题目描述：
给你一个产品数组 products 和一个字符串 searchWord ，products  数组中每个产品都是一个字符串。

请你设计一个推荐系统，在依次输入单词 searchWord 的每一个字母后，推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个，请按字典序返回最小的三个。

请你以二维列表的形式，返回在输入 searchWord 每个字母后相应的推荐产品的列表。

 

示例 1：

输入：products = [“mobile”,”mouse”,”moneypot”,”monitor”,”mousepad”], searchWord = “mouse”
输出：[
[“mobile”,”moneypot”,”monitor”],
[“mobile”,”moneypot”,”monitor”],
[“mouse”,”mousepad”],
[“mouse”,”mousepad”],
[“mouse”,”mousepad”]
]
解释：按字典序排序后的产品列表是 [“mobile”,”moneypot”,”monitor”,”mouse”,”mousepad”]
输入 m 和 mo，由于所有产品的前缀都相同，所以系统返回字典序最小的三个产品 [“mobile”,”moneypot”,”monitor”]
输入 mou， mous 和 mouse 后系统都返回 [“mouse”,”mousepad”]
示例 2：

输入：products = [“havana”], searchWord = “havana”
输出：[[“havana”],[“havana”],[“havana”],[“havana”],[“havana”],[“havana”]]
示例 3：

输入：products = [“bags”,”baggage”,”banner”,”box”,”cloths”], searchWord = “bags”
输出：[[“baggage”,”bags”,”banner”],[“baggage”,”bags”,”banner”],[“baggage”,”bags”],[“bags”]]
示例 4：

输入：products = [“havana”], searchWord = “tatiana”
输出：[[],[],[],[],[],[],[]]  

提示：

1 <= products.length <= 1000
1 <= Σ products[i].length <= 2 * 10^4
products[i] 中所有的字符都是小写英文字母。
1 <= searchWord.length <= 1000
searchWord 中所有字符都是小写英文字母。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-suggestions-system
可以看到，题目要求中明确说明了products[i]中所有的字符都是小写英文字母，因此一颗标准的26叉的字典树便能很好的解决这一问题。当然，除了26叉这种暴力的解决方式外，使用哈希表也是一种很好的思路，本题LeetCode官方题解中的字典树便是利用和哈希表。但接下来我们还是以26叉树的思路来解决问题。字典树的结构已经很好的解决了题目对于前缀查询的要求，剩下需要解决的便是products数组中前缀与searchWord相同的最多三个产品并且按字典序返回最小的三个这一要求。我们可以在字典树中增加一个大小最多为三的优先队列，来保存符合当前前缀的单词，这一思路的来源便是第k大这一经典的问题。通过上述的修改，题目所要求的问题都得到了解决。
AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class Solution {
public:
struct node
{
    struct node *next[26];
    priority_queue<string,vector<string>,less<string>> words;
};
vector<vector<string>> ans;

node *creat()
{
    node *p=new node;
    for(int i=0;i<26;i++)
    {
        p->next[i]=NULL;
    }
    return p;
}

void three(node *head,string s)
{
    head->words.push(s);
    while(head->words.size()>3)  head->words.pop();
}

void insert(string s,node *head)
{
    int len=s.length();
    node *p=head;
    node *t=head;
    for(int i=0;i<len;i++)
    {
        int c=s[i]-'a';
        if(p->next[c]==NULL)
        {
            t=creat();
            p->next[c]=t;
            p=p->next[c];
            three(p,s);
        }
        else
        {
            p=p->next[c];
            three(p,s);
        }
    }
}

void search(string s,node *head,int x)
{
    node *p=head;
    int len=s.length();
    for(int i=0;i<len;i++)
    {
        int c=s[i]-'a';
        if(p->next[c]==NULL)  return;
        else
        {
            p=p->next[c];
        }
    }
    int temp=p->words.size();
    ans[x].resize(temp);
    for(int i=0;i<temp;i++)
    {
        string ch=p->words.top();
        ans[x][temp-1-i]=ch;
        p->words.pop();
    }
}

    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
    int n=products.size();
    node *root=creat();
    for(int i=0;i<n;i++)
    {
        insert(products[i],root);
    }
    int len=searchWord.length();
    vector<vector<string>> temp(len);
    ans=temp;
    string pre;
    for(int i=0;i<len;i++)
    {
        pre=pre+searchWord[i];
        search(pre,root,i);
    }
    return ans;
    }
};

执行用时: 284 ms
内存消耗: 147.5 MB

end☆~

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://misaka-network10032.github.io/2021/03/09/%E5%AD%97%E5%85%B8%E6%A0%91/

更新于：Apr 4, 2021

算法

c++

评论