Сложность: Hard
Дана строка s. Разделите строку так, чтобы каждая подстрока разделения была палиндромом.
Верните минимальное количество разрезов, необходимых для разделения строки s на палиндромы.
Пример:
Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
👨💻 Алгоритм:
1️⃣Определение задачи и начальные условия:
Алгоритм обратного отслеживания реализуется путём рекурсивного изучения кандидатов-подстрок. Мы определяем рекурсивный метод findMinimumCut, который находит минимальное количество разрезов для подстроки, начинающейся с индекса start и заканчивающейся на индексе end. Чтобы найти минимальное количество разрезов, мы также должны знать минимальное количество разрезов, которые были найдены ранее для других разделений на палиндромы. Эта информация отслеживается в переменной minimumCut. Начальное значение minimumCut будет равно максимально возможному количеству разрезов в строке, что равно длине строки минус один (т.е. разрез между каждым символом).
2️⃣Генерация подстрок и рекурсивный поиск:
Теперь, когда мы знаем начальные и конечные индексы, мы должны сгенерировать все возможные подстроки, начиная с индекса start. Для этого мы будем держать начальный индекс постоянным. currentEndIndex обозначает конец текущей подстроки.
3️⃣Условие палиндрома и рекурсивное разделение:
Если текущая подстрока является палиндромом, мы сделаем разрез после currentEndIndex и рекурсивно найдем минимальный разрез для оставшейся строки
😎 Решение:
class Solution:
def minCut(self, s: str) -> int:
return self.findMinimumCut(s, 0, len(s) - 1, len(s) - 1)
def findMinimumCut(self, s: str, start: int, end: int, minimumCut: int) -> int:
if start == end or self.isPalindrome(s, start, end):
return 0
for currentEndIndex in range(start, end + 1):
if self.isPalindrome(s, start, currentEndIndex):
minimumCut = min(
minimumCut,
1 + self.findMinimumCut(s, currentEndIndex + 1, end, minimumCut)
)
return minimumCut
def isPalindrome(self, s: str, start: int, end: int) -> bool:
while start < end:
if s[start] != s[end]:
return False
start += 1
end -= 1
return True
Ставь 👍 и забирай 📚 Базу знаний