# 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不是回文，就可以直接退出，从而减少计算量

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