Задача: 132. Palindrome Partitioning II
Сложность: 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 и рекурсивно найдем минимальный разрез для оставшейся строки

😎 Решение:

var minCut = function (s) {
    return findMinimumCut(s, 0, s.length - 1, s.length - 1);
};

var findMinimumCut = function (s, start, end, minimumCut) {
    if (start === end || isPalindrome(s, start, end)) {
        return 0;
    }
    for (let currentEndIndex = start; currentEndIndex <= end; currentEndIndex++) {
        if (isPalindrome(s, start, currentEndIndex)) {
            minimumCut = Math.min(
                minimumCut,
                1 + findMinimumCut(s, currentEndIndex + 1, end, minimumCut),
            );
        }
    }
    return minimumCut;
};

var isPalindrome = function (s, start, end) {
    while (start < end) {
        if (s[start++] !== s[end--]) {
            return false;
        }
    }
    return true;
};

Ставь 👍 и забирай 📚 Базу знаний