问个Facebook的面经题

原帖地址:mitbbs

3. 一种字母游戏这样的
给定四个位置 _,_,_,_
然后每个位置可以选5个candidates,然后问这些candidates最多可以组成多少个有效
的词,字典是给定的。

比如,
如果字典是 [cake, bike, fake]
我们可以这样选candidates
第一个位置可以选 b,c,f,e,d
第二个位置 i,a,o,p,e
第三个位置 k,m,w,q,a
第四个位置 e,g,h,k,l
那这些可以组成3个有效的词 cake, bike, fake.

但是如果,这样选每个位置的candidates
第一个位置可以选 z,c,v,b,y
第二个位置 i,a,o,p,e
第三个位置 k,m,w,q,a
第四个位置 e,g,h,k,l

只能组成一个有效的词就是bike.
这样就是第一种选candidates的方法比较好。

然后问你怎么选每个位置的candidates,最终可以让能组成的词最多。

没有什么特别好的思路,问是不是brutal search,还有更好的方法吗?答:你如果要
brutal search的话,你估算一下时间。
我就开始算时间,发现很长,然后面试官说,那你想办法优化。。。但是因为算brual
search的时间算了太长时间了,就没什么时间优化了。。。