131. Palindrome Partitioning

public class Solution {
    public IList<IList<string>> Partition(string s) {
        var ans = new List<IList<string>>();
        Dfs(0, new List<string>(), s, ans);
        return ans;
    }
    private void Dfs(int start, List<string> currentList, string s,
                     List<IList<string>> result) {
        if (start >= s.Length)
            result.Add(new List<string>(currentList));
        else {
            for (int end = start; end < s.Length; end++) {
                if (IsPalindrome(s, start, end)) {
                    currentList.Add(s.Substring(start, end - start + 1));
                    Dfs(end + 1, currentList, s, result);
                    currentList.RemoveAt(currentList.Count - 1);
                }
            }
        }
    }
    bool IsPalindrome(string s, int low, int high) {
        while (low < high)
            if (s[low++] != s[high--])
                return false;
        return true;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public IList<vector<string>> Partition(string s) {
        var ans = new List<vector<string>>();
        Dfs(0, new List<string>(), s, ans);
        return ans;
    }
    private void Dfs(int start, List<string> currentList, string s,
                     List<vector<string>> result) {
        if (start >= s.size())
            result.push_back(new List<string>(currentList));
        else {
            for (int end = start; end < s.size(); end++) {
                if (IsPalindrome(s, start, end)) {
                    currentList.push_back(s.Substring(start, end - start + 1));
                    Dfs(end + 1, currentList, s, result);
                    currentList.RemoveAt(currentList.size() - 1);
                }
            }
        }
    }
    bool IsPalindrome(string s, int low, int high) {
        while (low < high)
            if (s[low++] != s[high--])
                return false;
        return true;
    }
}

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<List<String>>();
        dfs(0, result, new ArrayList<String>(), s);
        return result;
    }

    void dfs(int start, List<List<String>> result, List<String> currentList, String s) {
        if (start >= s.length()) result.add(new ArrayList<String>(currentList));
        for (int end = start; end < s.length(); end++) {
            if (isPalindrome(s, start, end)) {
                currentList.add(s.substring(start, end + 1));
                dfs(end + 1, result, currentList, s);
                currentList.remove(currentList.size() - 1);
            }
        }
    }

    boolean isPalindrome(String s, int low, int high) {
        while (low < high) {
            if (s.charAt(low++) != s.charAt(high--)) return false;
        }
        return true;
    }
}

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;
    }
};

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []
        self.dfs(s, [], result)
        return result

    def isPalindrome(self, s: str) -> bool:
        return s == s[::-1]

    def dfs(self, s: str, path: List[str], result: List[List[str]]):
        if not s:
            result.append(path)
            return
        for i in range(1, len(s) + 1):
            if self.isPalindrome(s[:i]):
                self.dfs(s[i:], path + [s[:i]], result)

func partition(s string) [][]string {
    res := [][]string{}
    dfs(s, []string{}, &res)
    return res
}

func dfs(s string, path []string, res *[][]string) {
    if len(s) == 0 {
        *res = append(*res, append([]string(nil), path...))
        return
    }
    for i := 1; i <= len(s); i++ {
        if isPalindrome(s[:i]) {
            dfs(s[i:], append(path, s[:i]), res)
        }
    }
}

func isPalindrome(s string) bool {
    lo, hi := 0, len(s)-1
    for lo < hi {
        if s[lo] != s[hi] {
            return false
        }
        lo++
        hi--
    }
    return true
}

Explanation

Algorithm

1️⃣

Инициация рекурсивного обхода:

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

Итеративно генерируем все возможные подстроки, начиная с индекса start. Индекс end увеличивается от start до конца строки.

2️⃣

Проверка на палиндром и продолжение поиска:

Для каждой сгенерированной подстроки проверяем, является ли она палиндромом.

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

3️⃣

Возврат (Backtracking) и сохранение результатов:

Возвращаемся, если начальный индекс start больше или равен длине строки, и добавляем currentList в результат.

😎