Дана строка s, разделите s так, чтобы каждая подстрока раздела была палиндромом. Вернуть все возможные палиндромные разбиения s.
Строка палиндрома – это строка, которая читается так же, как в прямом, так и в обратном порядке.
Пример 1:
Input: s = "aab" Output: [["a","a","b"],["aa","b"]]
Пример 2:
Input: s = "a" Output: [["a"]]
Решение:
Мы попробуем разбить каждую часть и проверить, палиндром это или нет.
для «ab» -> [a,b], [ab] мы должны разбить два раза сначала после «a», а затем после «b».
аналогично для «aab» -> [a,a,b], [a,ab], [aa,b], [aab].
для каждого разреза нам нужно проверить палиндром.
Оптимизация:
Так как мы проверяем палиндром для одной и той же строки много раз, мы можем сохранить его для каждой вычисляемой строки.
Давайте код
Заключение:
Это проблема от 2 января 2022 года — Проблема дня на Leetcode, если вы хотите больше подобных, следите за обновлениями.
Прокомментируйте свои ценные мысли или любые предложения по модификации решения.
