我正在编写一个以电话号码作为输入的程序。它应该检查是否已经存在一个是我们新号码前缀的电话号码。 例如:
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;
}
const string& s
,以避免在函数内部使用字符串时进行复制。 - tadmanstd::set
会更快地处理。 - tadman