Geek asks and answers

Trie, prefix for phonenbbers

I am creating a program that accepts phone numbers as input. Then you should check if there is a phone number in our new number, which is a prefix. Example:

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

I hope you understand what I get.

I implemented two functions:

Contains This should check if a number or prefixes exist.

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;
}

Embed

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;
}

Currently it only contains a check to see if the number has already been registered. I cannot find a good way to check if the prefix is ​​already a number. Should I implement it as part of, or possibly in, an insert function (maybe the loop goes through each prefix, starting from the first number?)

Any help was appreciated.

home

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;
}

Edit Insert:

    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

edit2:

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;
}
+3
source
2

PrefixStringSet::contains(string s)

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

, false , , temp - -NULL-.

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

, temp , s .
: temp != root, trie.

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 , , node .

+2

Trie Node, , .

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;
}

LEAF Node , Trie.

, , Node Node, , @timaru. .

+2

More articles:


All Articles