HDU1671——前缀树的一点感触

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

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

第一次Memory Limit Exceeded：

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

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

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

 ~Node()
 {
     for (int i = ; i < ; ++i)
     {
         if (children[i])
         {
             delete children[i];
             children[i] = nullptr;
         }
     }
 }

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

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

 vector<Node *> children;
 Node()
 {
     for (int i = ; i < ; ++i) children.push_back(nullptr);
 }

改成了

 vector<Node *> children = vector<Node *>(, nullptr);
 Node()
 {
     //for (int i = 0; i < 10; ++i) children.push_back(nullptr);
 }

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

附代码：

 #include <string>
 #include <vector>
 #include <iostream> using namespace std; class Node
 {
 public:
     bool is_phone = false;
     vector<Node *> children = vector<Node *>(, nullptr);
     Node()
     {}
     ~Node()
     {
         for (int i = ; i < ; ++i)
         {
             if (children[i])
             {
                 delete children[i];
                 children[i] = nullptr;
             }
         }
     }
     void insert(const string &_Phone)
     {
         Node *p = this;
         for (int i = ; i < _Phone.size(); ++i)
         {
             int curr = _Phone[i] - '';
             if (p->children[curr] == nullptr)
             {
                 p->children[curr] = new Node();
             }
             p = p->children[curr];
         }
         p->is_phone = true;
     }
     bool has_phone(const string &_Phone)
     {
         Node *p = this;
         for (int i = ; i < _Phone.size(); ++i)
         {
             int curr = _Phone[i] - '';
             if (!p->children[curr]) return false;
             if (p->children[curr]->is_phone) return true;
             p = p->children[curr];
         }
         return true;
     }
 }; typedef Node *Trie; int main()
 {
     int t;
     cin >> t;
     while (t--)
     {
         Trie trie = new Node();
         int n;
         cin >> n;
         string phone;
         bool flag = true;
         while (n--)
         {
             cin >> phone;
             if (trie->has_phone(phone)) { flag = false; }
             trie->insert(phone);
         }
         if (flag) cout << "YES" << endl;
         else cout << "NO" << endl;
         delete trie;
     }
     //system("pause");
     return ;
 }