python - 识别 5 个 "forbidden"字符，这些字符导致*最少*从单词列表中排除

Question

来自“Think Python”——作者提供了单词过滤练习(任务是根据最小长度、需要的字符或禁止的字符等从列表中包含/排除单词)

他增加了一个额外的问题:你能找到排除最少单词数的 5 个禁用字母的组合吗？ (我在这里和其他地方找到了与上述练习相关的主题，但不是这个额外问题的算法/答案。)这是我开始解决这个问题的地方，以及我遇到困难的地方:

1. 对于单词列表中的每个字符，标识其占用的单词数

2. 用每个键 = 给定字符构建一个字典；每个键值=该字符占用的总字数。

3. 按值排序以识别占用最少单词数的 5 个字符(按升序排列)。

我在这一点上有点卡住了——因为如果字符以各种组合的形式同时出现在某些单词中，这可以减少它们导致从该列表中排除的单词总数。

我不确定如何遵循该推理来“抽象”问题并找出通用解决方案。任何指针？

Answer 1

您的方法会找到禁止字符集的上限。您可以使用集合和集合并集来找出是否有一组字符比您的上界集合更好。

以下方法应该可行，但会创建大型集合:

• 创建一个字典，其中 26 个字母作为键，一个空集作为值。阅读单词并将它们添加到它们包含的字母的集合中。

• 找到五个最小单词集的字母。这些字母的设定长度之和就是您的上限。从字典中过滤出集合大于该上限的所有字母。

• 现在找出剩余字母中五个字母的所有组合的并集，并找出其并集最小的一个。您可以递归地执行此操作。