LC 131 Parlindrome Partitioning(M)

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. For example, given s = "aab", Return [ ["aa","b"], ["a","a","b"] ]

边界条件

解题思路

-求所有答案，首先排除动态规划，应该是DFS (Palindrome Partitioning II 求个数才是动归） -遇到要求所有组合、可能、排列等解集的题目，一般都是DFS + backtracking -首先传入s="aab" path=[] res = [], 首先切割出"a"（然后是"aa" "aab" ...），然后判读它是不是回文串： 如果不是，直接跳过 如果是，则此时剩余的 s="ab"， path += ["a"] 写入res的判断是，当s=""时，记录结果 -优化：可以通过用DP来计算任意s[i:j]是否是回文，并保存结果，再执行DFS，如果发现某条string不是回文，就可以直接退出，从而减少计算量

public List<List<String>> partition(String s) {
    List<List<String>> res = new ArrayList<>();
    if (s == null || s.length() == 0) return res;
    partition(res, new ArrayList<>(), s);
    return res;
}

private void partition(List<List<String>> res, List<String> list, String s) {
    if (s.length() == 0) {
        res.add(new ArrayList<String>(list));
        return;
    }
    //backtrack 方式查找回文
    for (int i = 0; i <= s.length(); i++) {
        String front = s.substring(0, i);
        //当前s(0,i) 是否是回文
        if (isPalindrome(front)) {
            list.add(front);
            // 递归判断 剩余s(i) 内的回文组合
            partition(res, list, s.substring(i));
            list.remove(list.size() - 1);
        }
    }
}
//判断字符串是否是回文
private boolean isPalindrome(String s) {
    if (s == null || s.length() == 0) return false;
    int lo = 0, hi = s.length() - 1;
    while (lo < hi) {
        if (s.charAt(lo) != s.charAt(hi)) return false;
        lo++;
        hi--;
    }
    return true;
}