Trie，電話號碼的前綴

Question

我建立一個以電話號碼作爲輸入的程序。然後它應該檢查在我們的新號碼中是否已經存在一個電話號碼，這是一個前綴。 例如：

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

希望你明白我在做什麼。

我已經實現了兩個功能：

包含 如果數量或前綴已經存在，那應該檢查。

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

，因爲它代表現在只包含檢查的，如果號已被註冊。我找不出一個好方法來檢查前綴是否已經是一個數字。 我應該實現它在包含或可能在插入功能（也許有一個循環去槽每個前綴，從第一個數字開始？）

任何幫助表示讚賞。

主要

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 

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

Answer 1

在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以避免陷入空樹狀結構。

TrieNode::hasAnyChild()的最有效實施取決於TrieNode::children是如何存儲的，而不是在問題陳述中顯示的。如果你的trie只接受十進制數字，那麼簡單地通過所有的孩子應該足夠好。

順便說一句，在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一步移動。

Answer 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節點表示現有的字，因爲你沒有允許任何數量要在這個特里另一個號碼的前綴。

因此，您可以通過@timaru所說的迭代其子節點來檢查節點是否爲葉節點。但它不是非常有效。