Trie，电话号码前缀

Question

Trie，电话号码前缀

3

我正在编写一个以电话号码作为输入的程序。它应该检查是否已经存在一个是我们新号码前缀的电话号码。例如：

Input:
555 //This is okay
5556888 //This is not okay because 555 is a registered number
556888 //this is okay
5568889 // Not okay

希望你能理解我的意思。

我实现了两个函数：

Contains 该函数应该检查数字或前缀是否已经存在。

bool PrefixStringSet::contains(string s)
{
    NodePtr temp = root;
    for ( int i = 0; i < s.size(); i++)
    {
        if(temp->children[s[i] - '0'] == NULL)
        {
            return false;
        }
        temp = temp->children[s[i] - '0'];
    }
    return true;
}

插入

bool PrefixStringSet::insert(string s)
{
    if(contains(s) == true)
    {
        return false;
    }
    NodePtr temp = root;
    for (int i = 0; i < s.size(); i++)
    {
        int number = (int)s[i] - (int)'0';
        if(temp->children[number] == NULL)
        {
            temp->children[number] = new TrieNode;
            temp = temp->children[number];
        }
    }
    return true;
}

目前的代码只能检查号码是否已经被注册。我无法想出一个好的方法来检查前缀是否已经是数字。我应该在contains函数中实现它，还是在insert函数中实现它（也许可以通过循环遍历每个前缀，从第一个数字开始）？任何帮助都将不胜感激。

主要内容。

int main()
{
    PrefixStringSet Phonenumber;
   int HowManyPhoneNumbers;
   cin >> HowManyPhoneNumbers;
   for(int i = 0 ; i<HowManyPhoneNumbers ; i++)
   {

       string temp;
       cin >> temp;
       if(Phonenumber.insert(temp) == true)
       {
           cout << "Yes" << endl;
       }
       else
       {
           cout << "NO" <<endl;
       }

   }
  return 0;
}

编辑插入：

    bool PrefixStringSet::insert(string s)
    {
       if(contains(s) == true)
        {
            return false;
        }
        NodePtr temp = root;
        for (int i = 0; i < s.size(); i++)
        {
            int number = (int)s[i] - (int)'0';
            if(temp->children[number] == NULL)
            {
                temp->children[number] = new TrieNode;
            }
            temp = temp->children[number];
        }
        return true;
    }

Contains:
bool PrefixStringSet::contains(string s)
{
    NodePtr temp = root;
    for ( int i = 0; i < s.size(); i++)
    {
        if(temp->is_leaf())
        {
            return false;
        }
        if(temp->children[s[i] - '0'] == NULL)
        {
            return false;
        }
        temp = temp->children[s[i] - '0'];
    }
    return true;
}

input:
 911
YES
9111 /Not working
Yes
91 //Working
NO

编辑2：

bool PrefixStringSet::contains(string s)
{
    NodePtr temp = root;
    for ( int i = 0; i < s.size(); i++)
    {
        if(temp->is_leaf())
        {
            return false;
        }
        if (temp !=root &&  temp->is_leaf())
        {
            return true;
        }
        if(temp->children[s[i] - '0'] == NULL)
        {
            return false;
        }
        temp = temp->children[s[i] - '0'];
    }
    return true;
}

- user3265963

通常这类方法的签名是 const string& s，以避免在函数内部使用字符串时进行复制。 - tadman

我不确定你为什么要费力计算trie（作业？），因为一个简单的允许前缀的std::set会更快地处理。 - tadman

2个回答

2

在标准Trie中，您应该在节点结构中有另一个字段来指示它是否表示一个单词。

bool PrefixStringSet::contains(string s)
{
    NodePtr temp = root;
    for ( int i = 0; i < s.size(); i++)
    {
        if(temp->isWord)
        {
            return false;
        }
        if(temp->children[s[i] - '0'] == NULL)
        {
            return false;
        }
        temp = temp->children[s[i] - '0'];
    }
    return true;
}

bool PrefixStringSet::insert(string s)
{
    if(contains(s) == true)
    {
        return false;
    }
    NodePtr temp = root;
    for (int i = 0; i < s.size(); i++)
    {
        int number = (int)s[i] - (int)'0';
        if(temp->children[number] == NULL)
        {
            temp->children[number] = new TrieNode;
        }
        temp = temp->children[number];
    }
    temp->isWord = true;
    return true;
}

然而，在你的问题中，只有一个叶子节点表示存在一个单词，因为在这个Trie树中，你不允许任何数字成为另一个数字的前缀。因此，像@timaru所说，你可以通过迭代它的孩子来检查一个Node是否是叶子节点。但这并不是很有效率。

- Jun Zhou

我已经按照你的建议进行了调整，现在只能半正常地运行。只有当输入字符串比现有字符串短时才有效。请查看我的原始帖子中的更新。 - user3265963

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- timrau · Accepted Answer

在PrefixStringSet::contains(string s)中

    if(temp->children[s[i] - '0'] == NULL)
    {
        return false;
    }

不要直接返回 false，而应该检查 temp 是否有任何非空子节点。

    if(temp->children[s[i] - '0'] == NULL)
    {
        return (temp != root && temp->is_leaf());
    }

因为如果temp没有任何子节点，那么字符串s的前缀已经存在。
编辑：检查temp！= root以避免在空字典树中被卡住。 TrieNode :: hasAnyChild（）的最有效实现取决于如何存储TrieNode :: children，这在问题陈述中没有显示。如果您的字典树只接受十进制数字，则简单地遍历所有子节点就足够了。

顺便说一下，在PrefixStringSet :: insert（string s）中。

    int number = (int)s[i] - (int)'0';
    if(temp->children[number] == NULL)
    {
        temp->children[number] = new TrieNode;
        temp = temp->children[number];
    }

应该将代码行 temp = temp->children[number]; 放在 if 块结束后，因为无论是否创建了新节点，你都需要将 temp 向前移动一步。