学步园

小记：真的对不起自己。A完这题，让我感受很深，我用自己的错误换来了对Trie树的深度理解，这句话算是对自己的安慰吧，这题A的我很辛苦，我把输出的NO 打成No了，以至于浪费了许多时间在想Trie树的算法思想，以及变种，以及每一步是如何做，可以怎么做，用什么代码实现，哪种要快。我都试遍了，结果是我快要疯了，幸好在突然的某一瞬间，我想起了过去类似这样的情况，在自己的想法正确的情况下(自己首先要证明，至少得自己找不到错，而且没有不能用语言解释的步骤)，那么错误就应该是数据范围或者有输出的话就要考虑是否输出与题意不符等因素，想到这，我立马看了题目输出，顿时泪流满面，满脸沧桑，不容易啊，我在快疯的情况下，稳定了自己的情绪，努力想出我没有想到的可能情况，最后来个这样的，我想，这是一个深刻教训，我要好好反思，日后再碰到这样的情况，首先思维不能乱，在假设自己的想法的某方面正确的情况下，去验证算法的正确性，考虑数据的范围因素，题意输出正确与否的因素，以及题意是否理解清楚等等，而不是一味的磕死在代码上找问题。在一段时间内找不出代码表述的想法有问题的情况下，应该寻找其他方面的因素。必要的保证是头脑思维清晰，不然即便分析其他的因素也会很紊乱，可能导致躁乱，失去继续思维的耐心。谨记！

题解：题目有两种情况，当下一个号码数字需要开辟新空间来存的时候，从root节点到现在这个节点所表示的数字串是不是一个号码，如果是那就代表有前缀子串，返回NO就行；如果不是一个号码，那么现在要加入的这个号码肯定在之前没有那个号码是他的前缀，因此要标记起来。

第二种情况就是号码的数字一直匹配下去都不需要开辟空间，说明它就是某个号码的前缀。

在最后只需判断标记的变量是否标记过，没被标记那么就是第二种情况，返回NO，如果有被标记过，就代表它它是第一种情况的第二类，就返回YES，因为如果是第一种情况的第一类那么就直接返回NO了，后面的就不需要判断了。

下面贴上我的代码：不是用数组实现的，所以在速度上有些慢。

#include <string.h>
#include <iostream>

using namespace std;

#define MAX 10

typedef struct Node{
    bool isStr;
    struct Node *next[MAX];
    Node():isStr(false){//构造函数
        memset(next, NULL, sizeof(next));
    }
    ~Node(){//析构函数，如果用release函数释放的话就不要析构函数。用release，在速度上会慢上几十MS。
        for(int i = 0;i < MAX; ++i)
            if(next[i] != NULL)
                delete next[i];
    }
}TrieNode,*Trie;

Trie root;

int Insert(char *s){
    int flag = 0;
    TrieNode *p = root;

    while(*s){
        if(p ->next[*s-'0'] == NULL){
            if(p ->isStr){
                return 0;
            }
            p ->next[*s-'0'] = new TrieNode;
            flag = 1;
        }
        p = p ->next[*s-'0'];
        s++;
    }
    p->isStr = true;
    if(!flag) return 0;
    return 1;
}


void release(TrieNode *p){
    int i;
    for(i = 0; i < MAX; i++){
        if(p->next[i] != NULL){
            release(p->next[i]);
        }
    }
    delete p;
    return ;
}

int main() {
    char s[MAX*2];
    int Case, T, flag;
    cin >> Case;
    while(Case--){
        cin >> T;
        root = new TrieNode;
        flag = 1;
        while(T--){
            cin >> s;
            if(flag)
            flag = Insert(s);
        }
        if(!flag){
            cout <<"NO"<< endl;
        }
        else cout <<"YES"<< endl;
        //release(root);
        delete root;
    }
}