题目http://acm.hdu.edu.cn/showproblem.php?pid=1671

题目本身不难，一棵前缀树OK，但是前两次提交都没有成功。

第一次Memory Limit Exceeded：

前缀树是很费空间的数据结构，每个节点存放了字母（数字）个数个指针，正所谓用空间来换取时间。

我发现我忘记写析构函数了，所以测例多起来还不释放很容易超空间。

树形结构的析构也很有趣：

1 ~Node() 2 { 3     for (int i = 0; i < 10; ++i) 4     { 5         if (children[i]) 6         { 7             delete children[i]; 8             children[i] = nullptr; 9         }10     }11 }

好了，第二次没成功，Time Limit Exceeded：

看起来这是一棵规规矩矩的前缀树，仔细找可以优化的地方，试探性地把

1 vector
     
       children;2 Node()3 {4     for (int i = 0; i < 10; ++i) children.push_back(nullptr);5 }
     

改成了

1 vector
     
       children = vector
      
       (10, nullptr);2 Node()3 {4     //for (int i = 0; i < 10; ++i) children.push_back(nullptr);5 }
      
     

Accepted！显然构造的时候赋值比构造之后再赋值要快。。果然还是要尽可能的优化啊！

附代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4  5 using namespace std; 6  7 class Node 8 { 9 public:10     bool is_phone = false;11     vector
        
          children = vector
         
          (10, nullptr);12     Node()13     {}14     ~Node()15     {16         for (int i = 0; i < 10; ++i)17         {18             if (children[i])19             {20                 delete children[i];21                 children[i] = nullptr;22             }23         }24     }25     void insert(const string &_Phone)26     {27         Node *p = this;28         for (int i = 0; i < _Phone.size(); ++i)29         {30             int curr = _Phone[i] - '0';31             if (p->children[curr] == nullptr)32             {33                 p->children[curr] = new Node();34             }35             p = p->children[curr];36         }37         p->is_phone = true;38     }39     bool has_phone(const string &_Phone)40     {41         Node *p = this;42         for (int i = 0; i < _Phone.size(); ++i)43         {44             int curr = _Phone[i] - '0';45             if (!p->children[curr]) return false;46             if (p->children[curr]->is_phone) return true;47             p = p->children[curr];48         }49         return true;50     }51 };52 53 typedef Node *Trie;54 55 int main()56 {57     int t;58     cin >> t;59     while (t--)60     {61         Trie trie = new Node();62         int n;63         cin >> n;64         string phone;65         bool flag = true;66         while (n--)67         {68             cin >> phone;69             if (trie->has_phone(phone)) { flag = false; }70             trie->insert(phone);71         }72         if (flag) cout << "YES" << endl;73         else cout << "NO" << endl;74         delete trie;75     }76     //system("pause");77     return 0;78 }