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

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

Даны две двоичные строки A и B длины N , задача состоит в том, чтобы подсчитать минимальное количество операций, необходимых для того, чтобы сделать две заданные строки равными, либо заменив местами соседние символы, либо перевернув любой символ строки A .

Примеры:

Input: A = “100”, B = “001”
Output: 2
Explanation: Flipping characters A[0](= ‘1’) and A[2](= ‘0’) modifies the string A to “001”, which is equal to the string B.

Input: A = “0101”, B = “0011”
Output: 1
Explanation: Swapping the characters A[2](= ‘0’) and A[3](= ‘1’) modifies the string A to “0011”, which is equal to string B.

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

  • Инициализируйте массив, скажем, dp[] размера N+1 как {0} , где dp[i] хранит минимальное количество операций, необходимых до индекса i, чтобы сделать префикс A i равным префиксу B i .
  • Переберите диапазон [1, N], используя переменную, скажем i , и выполняя следующие операции:
    • Если A[i – 1] равно B[i – 1], тогда обновите dp[i] до dp[i – 1] .
    • В противном случае обновите dp[i] до dp[i – 1] + 1 .
    • Если обмен возможен, т. е. i > 1 и A[i – 2] равно B[i – 1] , а A[i – 1] равно B[i – 2], то обновите dp[i] до min (дп[я], дп[я – 2] + 1).
  • После выполнения вышеуказанных шагов выведите минимальное количество полученных операций, т.е. значение dp[N].

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

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

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