时间戳

首页 > 解决方案 > 将唯一元素插入特里

trie - 将唯一元素插入特里

问题描述

void insert(struct node *root, string s)
{
    struct node *temp = root;
    for(int i=0;i<s.length();i++)
    {
        if(temp->idx[s[i]-'a']==NULL)
            temp->idx[s[i]-'a']=create();
        temp = temp->idx[s[i]-'a'];
        (temp->cnt)++;
    }
    temp->end=1;
}

所以我要插入字符串来创建一个唯一的 trie 数据结构，但是这个插入算法无法检测到任何重复的字符串，有人可以帮我这个插入算法如何仅用于插入唯一元素吗？

标签： trie

解决方案

您可以使用end. struct node让我们调用 find这个布尔方法并将其添加为insert方法的第一行。

bool find(struct node *root, string s)
{
    struct node *temp = root;
    for(int i=0;i<s.length();i++)
    {
        if(temp->idx[s[i]-'a']==NULL)
            return false;
        temp = temp->idx[s[i]-'a'];
    }
    return temp->end;
}

void insert(struct node *root, string s)
{
    if(!find(root, s)) return;
    struct node *temp = root;
    for(int i=0;i<s.length();i++)
    {
        if(temp->idx[s[i]-'a']==NULL)
            temp->idx[s[i]-'a']=create();
        temp = temp->idx[s[i]-'a'];
        (temp->cnt)++;
    }
    temp->end=1;
}

运行时：与之前相同，O(m)其中.ms

注意：我制定了find方法，因为无论如何你最多需要遍历两次 trie 的路径。一种方法是在开头提到的，第二种方法是end在您拥有代表的节点时检查重复项（属性）s，如果它确实是一个重复的字符串，那么您再次遍历s路径来修复属性中额外的 +1 cnt。

推荐阅读