拼字游戏解决最高分

Question

我被问到一个问题

您将获得一个字符列表,与每个字符相关的分数和有效单词的字典(比如普通英语字典).你必须从字符列表中形成一个单词,使得分数最大并且单词有效.

我可以想到一个解决方案,包括用字典制作的trie和带有可用字符的回溯,但是无法正确表达.有谁知道正确的方法或想出一个？

Answer 1

首先迭代你的字母并计算每个字符在英文字母表中出现了多少次。将其存储在静态中，例如char大小为 26 的数组，其中第一个单元格对应于a第二个单元格b，依此类推。将此原始数组命名为cnt。现在迭代所有单词，并为每个单词形成一个大小为 26 的类似数组。对于该数组中的每个单元格，检查 中是否至少有同样多的出现次数cnt。如果是这样的话，你可以写这个词，否则你不能。如果你能写出这个单词，你就可以计算它的分数并最大化辅助变量中的分数。

这种方法将具有线性复杂度，这也是您可能拥有的最佳渐近复杂度（毕竟您给出的输入是线性大小的）。