中大sicily 1426. Phone List 解题报告

1.原题中文大意;

给出一组数字，最多一万个，判断这组数字中是否存在一个数字是其它一个数字的前缀。

2.算法思想及解题用到的主要数据结构;

每读入一个数字字符串，则把该数字串从高位到低位分解成一个个数字字符。然后开始以最高位数字为树的根，第二个数字为根的子孙结点，第三个数字为第二个数字的子孙结点。如果碰到最后一个数字，如果这组数字符合要求的话则最后一个数字字符一定是叶子结点。不断的加入新的数字字符串到树中，如果在加入的过程中使以前的叶子结点变成了非叶子结点，或者新加入的数字字符串的最后一个数字在树中不是一个叶子结点，则报告这组数字字符串不符合要求。反之，则符合要求。

3.逐步求精算法描述（含过程及变量说明）;

每个结点记下关键信息,一个数字字符。再加上一个指向其它信息的指针. 这个指针指向一个node_data_t结构。结构体中放置了一个tag标签，记字是不是一个数字字符串的最后一个数字；以及一个指向STL的set容器，容器中放置了所有子孙结点。如下代码描述。

struct node_t

{

char _ch;

node_data_t* _data;

};

struct node_data_t

{

set _nodes;

bool _terminal;

};

剩下的逻辑便是分析数字字符串，把每个字符拆出加入树中。

4.程序注释清单

#include <set>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
struct node_comp;
struct node_data_t;
struct node_t
{
char _ch;
node_data_t* _data;
};
struct node_comp  // 给STL的set容器的排序算子。
{
bool operator()(const node_t& left, const node_t& right)const
{
return left._ch < right._ch;
}
};
http://ykyi.net zausiu's blog
struct node_data_t
{
set<node_t, node_comp>  _nodes;
bool _terminal;  // 标记是不是一个电话号码的终点字符了。
};
typedef set<node_t, node_comp> nodes_set;
nodes_set top_nodes;
// 如果已经可以判断电话号码不满足要求就返回false.
// 递归调用该函数。
bool odyssey(nodes_set& nodes, const char* num)
{
if ( 0 == *num )
{
return true;
}
//
node_t node;
node._ch = *num;
node._data = new node_data_t;
node._data->_terminal = !num[1];
pair<nodes_set::iterator, bool> retval = nodes.insert(node);
if ( retval.second )  // 还没有这个数字的结点.新插入的.
{
bool b;
b = odyssey(retval.first->_data->_nodes, num+1);
return b;
}
else  // 已经存在
{
delete node._data;
// 并且已经是之前一个数字串的最后一个数字字符.或者现在这个字符是最后一个.
if ( retval.first->_data->_terminal || !num[1] )
{
return false;
}
else if ( !num[1] )
{
retval.first->_data->_terminal = true;
return true;
}
else
{
retval.first->_data->_terminal = false;
bool b;
b = odyssey(retval.first->_data->_nodes, num+1); // 递归
return b;
}
}
}
// 释放内存.
void free_mem(nodes_set& nodes)
{
for ( nodes_set::const_iterator ite = nodes.begin();
ite != nodes.end();
++ite )
{
free_mem(ite->_data->_nodes);
delete ite->_data;
}
nodes.clear();
}
int main(int argc, char* argv[])
{
int case_count;   // 有多少个case
int phone_num_count;    // 多少个电话霖巴
char phone_num_str[11];   // 存电话霖巴
bool successed;  // 一组数字字符串是否符合要求
scanf("%d", &case_count);
for ( int i = 0; i < case_count; i++ )
{
scanf("%d", &phone_num_count);
successed = true;
for ( int j = 0; j < phone_num_count; j++ )
{
scanf("%s", phone_num_str);
if ( successed )
{
successed = odyssey(top_nodes, phone_num_str);
}
}
if ( successed )
{
printf(“YES\n”);
}
else
{
printf(“NO\n”);
}
free_mem(top_nodes);
}
return 0;
}

5.测试数据

用简单的脚本帮助生成测试数据.

#!/bin/bash

INDEX=0

if [ -e $1 ];then

COUNT=200

else

COUNT=$1

while [ $INDEX -lt $COUNT ];do

let "INDEX=$INDEX+1"

echo $RANDOM

done

6.对时间复杂度，空间复杂度方面的分析.

本算法的时间复杂度的空间复杂度一般都介于O(logN)和O(N)之间。

//////////////// 原题 //////////////

1426. Phone List

Description

Given a list of phone numbers, determine if it is consistent in the sense that no number is the pre?x of another. Let’s say the phone catalogue listed these numbers:

? Emergency 911

? Alice 97 625 999

? Bob 91 12 54 26

In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the ?rst three digits of Bob’s phone number. So this list would not be consistent.

Input

The ?rst line of input gives a single integer, 1 ≤ t ≤ 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 ≤ n ≤ 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

Output

For each test case, output “YES” if the list is consistent, or “NO” otherwise.

Sample Input

911

97625999

91125426

113

12340

123440

12345

98346

Sample Output

YES