[plain]
題意：給你的電話號碼當中，若出現一個電話的前綴是另一個電話則輸出NO，不存在則輸出YES
思路：想暴力？你爆的不止是時間，而且還爆空間
題解：字典樹，一個相當有用的數據結構，時間空間都無壓力，字典樹上的一個改動就在結構體加一個字符結束的標記即可
[plain]
[plain]
#include
#include
using namespace std;
struct Trie{
struct Trie *child[10];
bool isPerfix;
}*root;//字典樹
class Trie_Function{
public:
Trie* Trie_Init();//創建新結點並初始化
int Trie_Search(char *ch);
void Trie_Insert(char *ch);
};
Trie* Trie_Function::Trie_Init(){
Trie *node = new Trie;
for(int i = 0; i<10; i++)
node->child[i] = NULL;
node->isPerfix = false;
return node;
}
void Trie_Function::Trie_Insert(char *ch){
Trie *newNode,*nowNode;
int len = strlen(ch);
nowNode = root;
for(int i = 0; i
if(nowNode->child[ch[i]-'0']!=NULL){//存在
nowNode = nowNode->child[ch[i]-'0'];
}else{
newNode = Trie_Init();
nowNode->child[ch[i]-'0'] = newNode;
nowNode = newNode;
}
if(i == len - 1) nowNode->isPerfix = true;
}
}
int Trie_Function::Trie_Search(char *ch){
int len = strlen(ch);
Trie *nowNode = root;
bool flag = 0;
for(int i = 0; i
if(nowNode->child[ch[i]-'0']){//已存在
if(nowNode->isPerfix == true)//標記
{
flag = 1;
break;
}
else
nowNode = nowNode->child[ch[i]-'0'];
}
else{
return 0;
}
}
return flag;
}
void freedom(Trie *p)
{
for(int i = 0; i<10; i++)
if(p->child[i]!=NULL)
freedom(p->child[i]);
free(p);
}
int main()
{
char list[10010][15];
Trie_Function f;
char number[15];
int T,n;
cin>>T;
while(T--)
{
root = f.Trie_Init();//初始化根節點
cin>>n;
getchar();
for(int i = 0; i
{
gets(number);
f.Trie_Insert(number);
strcpy(list[i], number);
}
int temp = 0;
for(i = 0; i
{
strcpy(number, list[i]);
temp = f.Trie_Search(number);
if(temp)
{
cout<<"NO"<
break;
}
}
if(temp==0)
cout<<"YES"<
}
return 0;
}
