Количество способов очистить заданную строку путем рекурсивного удаления всех соседних дубликатов

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

Для заданной строки S за один ход можно удалить два соседних одинаковых символа . После удаления соединяются обе конечные точки удаленных символов. Подсчитайте общее количество способов очистить строку.

Пример:

Input: S = aabccb
Output: 3
Explanation:
1. aabccb -> aabb -> aa 
2. aabccb -> aabb -> bb
3. aabccb -> bccb -> bb
Hence, there are a total of 3 ways to empty the string after a valid set of moves.

Input: S = aabbc
Output: 0
Explanation: The string is of odd length, so it is not possible to empty the whole string.

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

  • Давайте определим двумерную таблицу dp dp[i][j], в которой будет храниться ответ для диапазона [i, j].
  • Определите рекурсивный подход к решению проблемы.
  • Чтобы вычислить dp[i][j] , выполните цикл по всем индексам k между i и j , где S[i] = S[k] .
  • Теперь для отдельного k ответ будет dp[i+1][k-1]*dp[k+1][j]*(Общее количество способов упорядочить удаления диапазона).
  • Чтобы вычислить последний член уравнения, обратите внимание, что удаление всего диапазона [i+1, k-1] произойдет до удаления S[i] и S[k].
  • Таким образом, общее удаление в диапазоне будет (j – i + 1)/2 (поскольку два элемента удаляются одновременно). Из этих удалений нужно выбрать (j – k)/2 удаления.
  • Таким образом, окончательная формула будет

  • Используйте запоминание, чтобы не пересчитывать состояния снова.
  • Проверьте базовые случаи в рекурсивной функции.
  • Окончательный ответ будет dp[0][N-1]

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

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

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