今天做了两道水题,要多水有多水...
其中有一道题是这样子的:
(6) 已知手机按键上数目到字母的映射:( 除了 "Q" 和 "Z")
给你一份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: 短发的小德把长发的纳豆横扫了,看来以后都留不了长发了..
[…] 汉语词典中词组不下十万行,就算是我们日常用到的词组,也不下2万行,如果你使用的输入法支持词典导出功能的话(大部分输入法是支持的),你可以亲自试试.在最最朴素的MM算法中,比如说前面运行了60多秒的vector版本,拖累算法效率的主要是词的存储.选择一个合适的数据结构是很重要的,事实上,你可以使用Trie树(这里,还有这里)来存储汉字词组,速度绝对飞快,可惜这样有点麻烦,这是由于汉字特殊的编码问题.与英文字符不同的是,汉字通用的编码是gb2312编码,每个汉字占两个字节,起始编码为OxB0A1,终止编码为OxF7FE(见下面的小程序).也许你会说,我们可以考虑使用哈希,但是这样的话也许会很耗内存,这我没有测试过,因为在用map测试之前,我发现set版本速度对我来说已经够用了,占用的内存也不多,600K左右.如果你有时间的话,强烈建议你试试哈希. […]