09.11.15 Programming >> , , 1 comment

今天做了两道水题,要多水有多水...

其中有一道题是这样子的:

(6)  已知手机按键上数目到字母的映射:( 除了 "Q" 和 "Z")

Trie

给你一份dict.txt,然后给你一串数字(长度最长为12),要求你从dict.txt中找出匹配的字符串.如,给出4734,则dict.txt中与之匹配的只有GREG.
[解] 看完题目我是吓到了.因为我以为这道题的数据规模会是很大,虽然3^12≈5*10^5不算是很大,但是如果测试数据有很多组的话,应该还是会TLE的.既然这样,那就只得对dict.txt建字典树了吧..对于这道题来说,建树过程是很容易的,每个节点有26个子节点,顺着字符串一路建下去就OK了.但是,有点麻烦的是,对输入的一串数字,如何查找出与之匹配的所有字符串.一般的字典树查找的确定性是明显的,存在就是存在,不存在就不存在.而这题中,根据映射关系,一个数字是对应于3个字母的,因此实际上的查找需要用到搜索,对于每一数字,遍历它的3种可能..我写字典树时就卡在这里了,然后很无聊的想了下,这么做实际上复杂度就变成了1+3^1+3^2+...+3^len=3^(len+1),而一般的字典树的复杂度为O(len),因此其实还不如暴力来得快...在一筹莫展的时候,突然发现漏读了题目的数据规模了,测试数据竟然只有一个,于是直接将dict.txt中每一行字符串转为数字串看是否与目标相同就行了..大汗..

迅速秒完水题,觉得写了不短时间的字典树代码不能浪费了,于是修改了下,部分代码贴在下面:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

#define max_num 26
 
struct node
{    
     bool is_word ; // 根到该节点是否对应一个字符串
     node *next[max_num];
     node()
     {
         is_word = false;
         for(int i = 0;i<max_num;i++)
              next[i] = NULL;
     }
};
 
class Trie
{
public:
 
     node *root;  //根节点
 
     Trie(){root = NULL;}
 
     bool search(const string str) //查找
     {
         node *location = root;
         for(int i = 0;i<str.length();i++)
         {
              if(location->next[str[i]-'a'] == NULL)
                   return false;
              location = location->next[str[i]-'a'];
         }
         return location->is_word;
     };
 
     void insert(const string str)    //插入
     {
         if(root == NULL)
              root = new node;
         node *location = root;
         for(int i = 0;i<str.length();i++)
         {
              int site = str[i] - 'a';
              if(location->next[site] == NULL)
              {
                   location->next[site] = new node;
                   location = location->next[site];
              }
              else
                   location = location->next[site];
         }
         location->is_word = true;
     };
 
 
     bool del(const string str)       //删除
     {
         node *location = root;
         for(int i = 0;i<str.length();i++)
         {
              if(location->next[str[i]-'a'] == NULL)
                   return false;
              location = location->next[str[i]-'a'];
         }
         if(location->is_word)
              location->is_word  = false;
         else
              return false;
         return true;
     }
 
};

PS: 短发的小德把长发的纳豆横扫了,看来以后都留不了长发了..