Наименьшее количество слов, необходимых для создания целевой строки

Опубликовано: 22 Сентября, 2022

Дан массив строк, words[] размера M и цель строки размера N . Задача состоит в том, чтобы найти минимальное количество слов , необходимых для составления целевой строки, вырезая отдельные буквы из набора слов и переставляя их, при условии, что запасы каждого слова бесконечны. Если это невозможно, выведите -1.

Примеры:

Input: words[] = {“with”, “example”, “science”}, target = “thehat”
Output: 3
Explanation: The target string, “thehat” consists of {‘h’ = 2, ‘t’ = 2, ‘e’ = 1, ‘a’ = 1}.
The two “with” strings are required to get two ‘h’ and two ‘t’ and one “example” string is required to get one ‘e’ and one ‘a’ to form the target string “thehat”.
So, total word required to construct the given target is 3.

Input: words[] = {“notice”, “possible”}, target = “basicbasic”
Output: -1
Explanation: It is not possible to form the given target string.

Подход: Идея состоит в том, чтобы использовать возврат. Следуйте инструкциям, чтобы решить проблему:

  • Объявите двумерный массив, скажем, countMap[][], где countMap[i][j] хранит количество j -х символов в i -й строке.
  • Объявите массив charAvavilable[26], обозначающий текущее количество доступных символов.
  • Определите рекурсивную функцию, которая принимает текущий индекс i (первоначально 0) строки target в качестве входных данных.
    • Если текущий счет больше, чем общий счет, то возврат. Кроме того, если текущий индекс i равен N , обновите общее количество и верните значение.
    • Если есть вхождение target[i] в charAvailable[] ,
      • Уменьшите вхождение символа target[i] в charAvailable[] .
      • Рекурсивно вызывать индекс i+1 , одновременно обновляя count на 1.
      • Увеличьте вхождение символа target[i] на 1 после вызова функции для поиска с возвратом.
    • В противном случае повторите countMap[][], чтобы найти вхождение target[i] . Если найдено, рекурсивно вызовите функцию, обновив счетчик на 1, а также выполните шаг возврата после вызова функции.
  • Выведите минимально необходимое количество слов.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(M*26*2 N )
Вспомогательное пространство: O(M*26)

РЕКОМЕНДУЕМЫЕ СТАТЬИ