Задача: 131. Palindrome Partitioning
Сложность: medium

Дана строка s. Разделите строку таким образом, чтобы каждая подстрока разделения была палиндромом. Верните все возможные варианты разделения строки s на палиндромы.

Пример:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

👨‍💻 Алгоритм:

1️⃣Инициация рекурсивного обхода:
В алгоритме обратного отслеживания (backtracking) мы рекурсивно пробегаем по строке, используя метод поиска в глубину (depth-first search). Для каждого рекурсивного вызова задаётся начальный индекс строки start.
Итеративно генерируем все возможные подстроки, начиная с индекса start. Индекс end увеличивается от start до конца строки.

2️⃣Проверка на палиндром и продолжение поиска:
Для каждой сгенерированной подстроки проверяем, является ли она палиндромом.
Если подстрока оказывается палиндромом, она становится потенциальным кандидатом. Добавляем подстроку в currentList и выполняем поиск в глубину для оставшейся части строки. Если текущая подстрока заканчивается на индексе end, то end+1 становится начальным индексом для следующего рекурсивного вызова.

3️⃣Возврат (Backtracking) и сохранение результатов:
Возвращаемся, если начальный индекс start больше или равен длине строки, и добавляем currentList в результат.

😎 Решение:

var partition = function (s) {
    const res = [];
    dfs(s, [], res);
    return res;
    function dfs(s, path, res) {
        if (!s.length) {
            res.push(path);
            return;
        }
        for (let i = 0; i < s.length; i++) {
            const cur = s.substr(0, i + 1);
            if (isPalindrome(cur)) {
                dfs(s.substr(i + 1), path.concat(cur), res);
            }
        }
    }
    function isPalindrome(s) {
        let lo = 0,
            hi = s.length - 1;
        while (lo < hi) {
            if (s[lo++] != s[hi--]) return false;
        }
        return true;
    }
};

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