猜一个五位的单词 - 要求起猜的单词
预先给定 dictionary
比如单词实际是 tires
你猜了apple，就返回 —e-
再猜 boxes, 返回 —es
再猜 times, 返回 ti-es
最后猜 tires，返回 tires
问given dictionary of List，如何选择第一个猜的单词
这题要求在dictionary选一个开始猜的单词
谷歌猜词题目 微信群上的聊天记录如下，请查收。
————— 2019-01-27 —————
恭贺 12:02
假设每个单词，与dictionary中的k个单词有相同字母，那么选k最大的单词。
恭贺 12:02
如果k相同，我就不清楚了
X 12:02
举个例子吧，没看懂
恭贺 12:04
比如apple与其他几个单词都没有相同位置相同字母
X 12:04
你这个runtime太高了吧
X 12:04
dictionary有n个单词的话
恭贺 12:05
有个问题，那个Apple为什么会返回e，它的e的位置跟tires不一样啊
X 12:06
只要letter碰到
X 12:07
位置会自动纠正
X 12:07
其实看你hit了几个letter
X 12:07
猜词也是从这点入手
恭贺 12:08
原来如此
目的是要最少次数猜到吗？List有多大？如果list很大的话用sort来找最长的单词好像很2。。
List 的size是n，那么你的算法要做到 runtime O(n)
sort 确实会更大
说一下思路吧，其实就是一个算 score 的机制：
- 先统计每个letter的频率，计算一个 count map，即 Map<Character, Integer> count。同时记下出现过的最大频率，即 max。
- 对每个 word 计算 score， 选 score 最高的 word。
如何计算 score ？
这个仁者见仁，智者见智。可以用count map，对每个letter 的 count 加到 score 中。因为重复的letter需要减分，我们可以对每出现一次重复，分数减掉一个 max。
runtime 是 O(n)， extra space 是 O(n)