pku3630 Phone List 字典树+判断前缀 经典入门题

题意：
给出一堆电话号码，判断是否存在某个号码是另一个号码的前缀

题解：
还是通过字典树，不过判断的时候不能够仅仅判断当前待插入字符串的路径上是否包含结束标记（如果事先对字符转进行了按长短排序就没问题了），而需要记录每个节点包含的路径条数，如果在待插入字符串的尾节点（即结束标记节点上通过的路径数大于1，则说明有路径覆盖了这个节点，即有一个字符转以当前字符串为前缀，故不可能）

代码：
 1import java.io.*;
 2class Dic_Tree
 3{
 4    class node
 5    {
 6        node nxt[]=new node[10];
 7        boolean end=false;
 8        int count=0;
 9    }
10    node head=null;
11    void clear()
12    {
13        head=new node();
14    }
15    boolean insert(String str)
16    {
17        node p=head;
18        for(int i=0;i<str.length();i++)
19        {
20            p.count++;
21            if(p.end) return false;
22            if(p.nxt[str.charAt(i)-48]==null)
23                p.nxt[str.charAt(i)-48]=new node();
24            p=p.nxt[str.charAt(i)-48];
25        }
26        p.count++;
27        if(p.count>1) return false;
28        p.end=true;
29        return true;
30    }
31    
32}
33public class Main {
34
35    /**
36     * @param args
37     */
38    static Dic_Tree data=new Dic_Tree();
39    public static void main(String[] args) throws IOException{
40        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
41        int test=Integer.parseInt(in.readLine());
42        while((test--)!=0)
43        {
44            int num=Integer.parseInt(in.readLine());
45            boolean flag=true;
46            data.clear();
47            while((num--)!=0)
48              if(flag)
49              {
50                if(!data.insert(in.readLine())) flag=false;
51              }
52              else
53                  in.readLine();
54            if(flag) System.out.println("YES");
55            else System.out.println("NO");
56            
57        }
58
59    }
60
61}
62

posted on 2011-01-12 00:11 yzhw 阅读(357) 评论(0)  编辑 收藏 引用 所属分类: data struct


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2011年1月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜