Задача: 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 в результат.

😎 Решение:

class Solution {
    func partition(_ s: String) -> [[String]] {
        var result = [[String]]()
        var currentList = [String]()
        dfs(&result, s, 0, &currentList)
        return result
    }

    private func dfs(_ result: inout [[String]], _ s: String, _ start: Int, _ currentList: inout [String]) {
        if start >= s.count {
            result.append(currentList)
        }
        for end in start..<s.count {
            if isPalindrome(s, start, end) {
                let range = s.index(s.startIndex, offsetBy: start)...s.index(s.startIndex, offsetBy: end)
                currentList.append(String(s[range]))
                dfs(&result, s, end + 1, &currentList)
                currentList.removeLast()
            }
        }
    }

    private func isPalindrome(_ s: String, _ low: Int, _ high: Int) -> Bool {
        var low = low
        var high = high
        let sArray = Array(s)
        while low < high {
            if sArray[low] != sArray[high] {
                return false
            }
            low += 1
            high -= 1
        }
        return true
    }
}

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