algorithm - 以最高分数解决拼字游戏

Question

有人问我一个问题

You are given a list of characters, a score associated with each character and a dictionary of valid words ( say normal English dictionary ). you have to form a word out of the character list such that the score is maximum and the word is valid.

我能想到一个解决方案，涉及由字典构成的 trie 和可用字符的回溯，但无法正确表述。有谁知道或想出正确的方法吗？

Answer 1

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

这种方法将具有线性复杂度，这也是您可能拥有的最佳渐近复杂度(毕竟您得到的所有输入都是线性大小)。