a1
我得到了一个非常大的单词数组(我们称之为)(比如dog
, fish
, run
,programming
任何东西)。
我可以将任何单词 outa1
与任何其他单词组合(例如,您可以组合dog
and programming
into dog-programming
),然后一次又一次,直到字符串变得非常大。
我还有一个a2
字符串数组(我们称之为 )(例如de
, s
, x?
, umh
,它们几乎可以是任何东西)。保证在a2
a1 的任何字符串中都没有找不到的字符串。
我正在寻找的是包含所有字符串的最短字符串(就创建该字符串所需的组合数量而言最短,而不是该字符串包含多少字符)a2
。如果有多个字符串都具有最小长度,我可以选择任何一个,然后退出程序。
现在,我不认为我可以暴力破解,因为即使数组相对较小,也有几乎无穷无尽的组合单词的选择,但我很想被证明是错误的!
有什么好的方法可以得到最短的字符串,肯定会产生最短的结果,还是我必须使用启发式算法来搜索相当短的字符串?
我尝试从 a1 中挑选一个覆盖 a2 中大多数字符串的字符串,然后从 a2 中删除这些项目,然后重新开始,但它不起作用!它产生了很好的结果,但不是最好的。