实现一个包含65535个单词的字典,在输入一个字符串后,能找出字符串中在字典中能匹配的所有单词。
这个一开始,考虑对26个字母进行编码,然后对单词进行数字化,最后只需要对字符串进行拆分,然后得到编码,然后去确定这个编码是否存在,即可得到字符串中的所有在字典中有定义的子串。
第二种考虑,就是对65535个单词做一个排序,按长度进行分类,初步估计,单词的长度最多为2~30,然后将单词按首字母进行二次分类,每一个长度都有26个不同的首字母,进行2次划分后,仍然存在少量单词。大概计算一下,65535/26=253, 可见每个长度下有253个单词,253/26=10,可见同一长度下每个首次字母开头的单词是10个。
如果这个单词我们采用map实现,而map内部是采用RB-Tree实现,二叉树中的元素的个数与树的深度关系是2^n-1,因为元素是10个,所以树的深度应该是4,不算太深,满足要求。
如果,字典中单词的个数达到10w级,这个设计考虑不能满足要求。这时也许要采用第一种方式解决。
阅读(581) | 评论(0) | 转发(0) |