Минимальное количество префиксов и суффиксов строки, необходимое для формирования данной строки

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

Даны две строки str1 и str2, задача состоит в том, чтобы найти минимальное количество префиксов и суффиксов из str2 , необходимых для формирования строки str1. Если задача невозможна, верните «-1».

Пример:

Input: str1 = “HELLOWORLD”, str2 = “OWORLDHELL”
Output: 2
Explanation: The above string can be formed as “HELL” + “OWORLD” which are suffix and prefix of the string str2

Input: str = “GEEKSFORGEEKS”, wrd = “SFORGEEK”
Output: 3
Explanation: “GEEK” + “SFORGEEK” + “S”  

Подход : Вышеупомянутая проблема может быть решена с помощью динамического программирования. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте массив dp , где i-й элемент arr[i] будет хранить минимальную конкатенацию, необходимую для формирования строки до индекса префикса i .
  • Инициализируйте dp[0] = 0 и другие значения массива dp равными -1 .
  • Инициализировать набор HashSet
  • Итерировать строку str1 слева направо и по каждому индексу i :
    • Добавьте подстроку от индекса 0 до текущего индекса i в набор HashSet.
  • Итерировать строку str1 справа налево и по каждому индексу i :
    • Добавьте подстроку из индекса i в конечный индекс в набор HashSet.
  • Проверьте все подстроки в строке str1 и соответственно обновите dp
  • Окончательный ответ будет храниться в dp[N], где N — длина строки str1 .

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

Временная сложность: O(N^2), где N — длина строки str1.
Вспомогательное пространство: O(N^2)

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