（讨论）百度2010校园招聘网络笔试题

皇家救星

原帖由 scu_guzo 于 2009-11-15 00:17 发表
回16楼：这4道题总共2小时。

回17楼：貌似不能去重吧，如ttrree则可以为tree，而且排序并直接遍历字典表的话也没有用树的效率高吧


嗯，目前的策略还是用树来解决。

为什么不能去重呢

从题目上没看出有限制字符使用个数

mcemil

原帖由 皇家救星 于 2009-11-17 12:53 发表


为什么不能去重呢

从题目上没看出有限制字符使用个数

去重肯定是错的，比如字典里有aabbcc，给出的字符窜abc，按你的做法，两边去重都是abc，也就是说abc能拼接出aabbcc，你觉得对吗？
而且你的做法和用字典树的方法没有本质区别。
一个是取便所有子集，判断每一个是否存在字典中。
而你的就是，取便多有字典，看是否是子集。
就目前的数量来看这两者的效率完全相同

snowboy9859

太复杂了

无法如愿

字典问题:

1, 去除字典内含有重复字母的单词 如 banana
   删除长度 大于 16 的单词

2, 先将字典内的每个单词 按字母排序重写  写个函数    string  sort_word( string)
    记录 转化前后对于关系   , 存在转化后的 一个string 对应 多个单词
    例如   sort  -转化成  orst  , word 转化成 dorw
    hash { orst } = [sort ], hash{ dorw } = [ word ]

3,  将要查询的 字母 按字母排序生成 string  , 在第2步 得到的数据结构中 查找是否存在 该 string
   考虑 字符组合, 存在 C( 16 ,16 ) +  C( 16 ,15 )  +  C( 16 ,14 )  +.... = 2^16 -1种可能
  即 最多查询 2^16 -1 次 (即 这16个字母无法组成单词 ) , 最少查询 1次 ( 刚好用到 16个字母)
  如果 查询结果  hash{ string } 得到的数组大小 不为 1 .  
  即存在多个单词符合条件

无法如愿

题目

百度2010校园招聘全国笔试题RD-3

2．一个单词字典库，单词个数约为10万，每个单词长度不超过16，单词都是由小写字母组成，同时给出16个小写字母，请设计一种高效算法来找到用这些给出字母拼出一个字典中最大长度的单词
。给出的16个字母每个字母最多使用一次，也可以不使用。存在多解的时候给出任意一个最优答案就行。

温馨提示：
1． 本次考试为闭卷考试，请保证独立完成试卷 ...
scu_guzo 发表于 2009-11-08 10:45

由于   给出的16个字母每个字母最多使用一次 也可以不使用
所以 去重