实现一个包含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级，这个设计考虑不能满足要求。这时也许要采用第一种方式解决。
阅读(579) | 评论(0) | 转发(0) |
