没有重复字母的最长单词序列

Question

我有一个单词列表。我需要选择其中没有重复字母的最长序列。比如我的话是：

ab
cd
cxyz

最长的序列是（6个字母）：

ab-cxyz

顺序不重要。我正在寻找一种选择此类序列的有效方法（至少包含 1000 个单词的列表）。

我尝试将 Knapsack problem 的解决方案修改为这个，但给出了错误的结果。

Answer 1

你创建一个这样的图表：你为每个单词创建一个节点，如果两个单词有一个共同的字母，你就用一条边连接它们。您还为每个节点分配了一个权重，即单词的长度。您现在正在搜索一组独立的节点，例如一组之间没有边的单词。你还需要这个独立的集合有一个最大的权重。

这是 maximum weight independent set problem 的一个实例，不幸的是这是一个 NP 难问题，没有任何已知的好的近似算法。