这1题,也是简单的字典树的利用,不过这里不是字母,而是数字。
题目的意思是判断输入的字符串会不会是其他字符串的前缀。就是这么的简单。
下面是AC的代码:
#include <iostream>
#include <cstring>
using namespace std;
class node //结点的结构体
{
public:
node* P[10];
};
node* root; //定义根节点
int ans; //叶子结点数
void insert(char* str) //插入操作的函数
{
int len = strlen(str);
node *q, *p;
q = root;
for(int i = 0; i < len; i++)
{
int id = str[i] - '0';
if(q->P[id] == NULL) //该位置不存在,new1个
{
p = new node;
for(int j = 0; j < 10; j++)
p->P[j] = NULL;
q->P[id] = p;
q = q->P[id];
}
else //存在,直接等于他的后继
q = q->P[id];
}
}
void fun(node *a) //递归找有多少个叶子结点
{
int flag = 0;
for(int i = 0; i < 10; i++)
{
if(a->P[i] != NULL)
{
flag = 1;
break;
}
}
if(!flag) //该结点是叶子结点,ans++
{
ans++;
return;
}
for(int j = 0; j < 10; j++)
if(a->P[j] != NULL)
fun(a->P[j]);
}
void dele(node *a) //删除操作的函数,也是递归完成
{
for(int i = 0; i < 10; i++)
if(a->P[i] != NULL)
dele(a->P[i]);
delete a;
}
int main()
{
// freopen("data.txt", "r", stdin);
int t, n;
char str[15];
cin >> t;
while(t--)
{
root = new node;
ans = 0;
for(int j = 0; j < 10; j++) //初始化根节点的指针数组P
root->P[j] = NULL;
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> str;
insert(str); //插入
}
fun(root); //算叶子结点数目
if(ans == n) //叶子结点等于输入的n 的个数,则YES
cout << "YES" << endl;
else //否则NO
cout << "NO" << endl;
dele(root); //删除
}
return 0;
}