题目描述

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例：
输入：s = “aab”
输出：[[“a”,”a”,”b”],[“aa”,”b”]]

题目分析

DFS，每一层对应一个回文子串。
维护右侧剩余长度 remain，DFS内枚举子串的长度。

Java

private List<List<String>> ans = new ArrayList<>();
private List<String> list = new ArrayList<>();

public List<List<String>> partition(String s) {
    dfs(s, s.length());
    return ans;
}

private void dfs(String s, int remain) {
    if (remain == 0) {
        ans.add(new ArrayList<>(list));
        return;
    }
    int start = s.length() - remain;
    for (int i = s.length() - remain; i < s.length(); i++) {
        if (isHuiWen(s, start, i)) {
            list.add(s.substring(start, i + 1));
            dfs(s, remain - (i - start + 1));
            list.remove(list.size() - 1);
        }
    }
}

private boolean isHuiWen(String s, int start, int end) {
    while (start <= end) {
        if (s.charAt(start) != s.charAt(end)) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

Kotlin

private val ans = ArrayList<List<String>>()
private val list = ArrayList<String>()

fun partition(s: String): List<List<String>> {
    dfs(s, s.length)
    return ans
}

private fun dfs(s: String, remain: Int) {
    if (remain == 0) {
        ans.add(ArrayList(list))
        return
    }

    val sb = StringBuilder()
    for (i in s.length - remain until s.length) {
        sb.append(s[i])
        val sub = sb.toString()
        val reversed = sub.reversed()
        if (sub == reversed) {
            list.add(sub)
            dfs(s, remain - (i - (s.length - remain) + 1))
            list.removeLast()
        }
    }
}