# [LeetCode 131] Palindrome Partitioning

### Question

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"]
]
```

### Stats

 Frequency 4 Difficulty 3 Adjusted Difficulty 4 Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

This is an extremely classic question.

It’s not very hard to solve, although it looked impossible at first.

### Solution

The solution is DFS.

It’s very standard DFS code, I will not go into coding details. This type of “return all possible path” question is always related to DFS, keep this in mind!

The code is borrowing ideas from peking2’s blog. He also had an analysis on this series of questions:

1. 最后结果是一个整数，比如Palindrome Partitioning II。这个用DP来解
2. 最后求一个结果，比如最小切法。这个用DP＋backtrack来解
3. 求所有的结果。这个一般用DFS来解。

This question is the 3rd case. Fish Lei also said the same.

### Code

``````public ArrayList<ArrayList<String>> partition(String s) {
// int len = s.length();
ArrayList<ArrayList<String>> ans = new ArrayList<ArrayList<String>>();
helper(ans, new ArrayList<String>(), s, 0);
return ans;
}

private void helper(ArrayList<ArrayList<String>> ans, ArrayList<String> cur,
String s, int start) {
int len = s.length();
if (start == len) {
return;
}
for (int i = start + 1; i <= len; i ++) {
String sub = s.substring(start, i);
if (isPal(sub)) {
helper(ans, cur, s, i);
cur.remove(cur.size() - 1);
}
}
}

private boolean isPal(String str) {
int left = 0, right = str.length() - 1;
while (left < right) {
if (str.charAt(left) != str.charAt(right))
return false;
left++;
right--;
}
return true;
}
``````