Я получил массив (назовем его a1) слов (таких как «собака», «рыба», «бег», «программирование» чего угодно), которые действительно огромны.
Я могу объединить любое из слов из a1 с любым другим из слов (например, вы можете объединить «собаку» и «программирование» в «собачье программирование»), а затем снова и снова, пока строки не станут действительно большой.
Я также получил массив (назовем его a2) строк (таких как "de", "s", "x?", "Umh", опять же, они могут быть практически любыми). Гарантируется, что в a2 нет строк, которые нельзя найти ни в одной из строк a1.
То, что я ищу, это самая короткая строка (самая короткая с точки зрения того, сколько комбинаций требуется для создания этой строки, а не сколько символов в этой строке), которая содержит все строки внутри a2. Если существует более одной строки, каждая из которых имеет минимальную длину, я могу просто выбрать любую и выйти из программы.
Теперь я не думаю, что смогу это просто перебрать, потому что, даже если массивы относительно малы, есть практически бесконечные варианты комбинирования слов, но я бы хотел оказаться ошибочным!
Есть ли какой-нибудь хороший способ получить самую короткую строку, которая, несомненно, даст самый короткий результат, или мне нужно использовать эвристические алгоритмы, чтобы просто искать довольно короткие строки?
РЕДАКТИРОВАТЬ: Я попытался просто выбрать строку из a1, которая покрывает большинство строк из a2, затем удалить эти элементы из a2, и начать снова, но это не работает! Это дает довольно хорошие результаты, но не лучшие.