Дана строка s. Нужно разбить строку на подстроки таким образом, чтобы каждая подстрока была палиндромом. Вернуть все возможные варианты разбиения на палиндромы.
Например, дана строка "aab". Возможные варианты разбиения на палиндромы:
Палиндром - это строка, которая читается одинаково в обоих направлениях. Например, "aba" - палиндром, а "abc" - нет.
Для решения задачи будем использовать рекурсивный подход. Напишем функцию, которая будет принимать строку и возвращать все возможные варианты разбиения на палиндромы.
Напишем функцию is_palindrome(s), которая будет проверять, является ли строка s палиндромом. Для этого будем сравнивать первый символ строки с последним, второй символ с предпоследним и т.д. Если все символы совпадают, значит строка является палиндромом.
Напишем функцию partition(s), которая будет вызывать рекурсивно сама себя, пока не найдет все возможные варианты разбиения на палиндромы.
Функция будет принимать на вход оставшуюся строку s и текущий список разбиений curr_partition. Если строка s пустая, значит мы нашли один из возможных вариантов разбиения на палиндромы и можем добавить текущий список разбиений в список результатов res.
Если строка s не пустая, будем перебирать все возможные подстроки s[:i] и проверять, является ли она палиндромом с помощью функции is_palindrome. Если подстрока является палиндромом, добавляем ее в текущий список разбиений curr_partition и рекурсивно вызываем функцию partition для оставшейся части строки s[i:]. После возврата из рекурсии удаляем добавленную подстроку из текущего списка разбиений.
Напишем код на Python:
class Solution:
def is_palindrome(self, s):
return s == s[::-1]
def partition(self, s):
res = []
curr_partition = []
def backtrack(s, curr_partition):
if not s:
res.append(curr_partition.copy())
return
for i in range(1, len(s)+1):
if self.is_palindrome(s[:i]):
curr_partition.append(s[:i])
backtrack(s[i:], curr_partition)
curr_partition.pop()
backtrack(s, curr_partition)
return res
s = "aab"
print(palindrome_partitioning(s))