algorithm - 查找包含指定集合中每个字符的最短单词组合

Question

我有一个单词数组(我们称它为 a1)(例如 dog、fish、run ，编程任何东西)真的很庞大。

我可以将 a1 中的任何单词与任何其他单词组合起来(例如，您可以将 dog 和 programming 组合成 dog-programming)，然后一次又一次，直到字符串变得非常大。

我还有一个字符串数组(我们称之为a2)(例如de、s、x?, umh，它们几乎可以是任何东西)。保证a2中没有在a1的任何字符串中都找不到的字符串。

我正在寻找的是包含 a2。如果有多个字符串都具有最小长度，我可以只选择一个，然后退出程序。

现在，我不认为我可以暴力破解它，因为即使数组相对较小，组合单词的选择几乎无穷无尽，但我很乐意被证明是错误的!

是否有任何好的方法来获得肯定会产生最短结果的最短字符串，或者我是否必须使用启发式算法来搜索非常短的字符串？

我尝试只从 a1 中挑选一个覆盖了 a2 中大部分字符串的字符串，然后从 a2 中删除这些项目，然后重新开始，但它不起作用!它产生了相当不错的结果，但不是最好的。

Answer 1

如果您像示例中那样将单词与破折号组合在一起，例如

dog + programming + sky = dog-programming-sky

AND A2中的单词不包含破折号，那么就是变相的SET-COVER，一个NP完全优化问题。然后，您可以使用任何可用于 SET-COVER 的解决策略来解决问题。 SET-COVER 有一个快速逼近算法，但如果您想获得绝对最小的解决方案，则需要求助于最坏情况指数算法。

如果您组合单词时没有破折号，例如

dog + programming + sky = dogprogrammingsky

那么问题就更难了，因为现在例如即使“ogpro”不是任何组成字符串的子字符串，也会在组合词中找到它。