Palindrome Partitioning

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example

given s = `"aab"`,
Return

```  [
["aa","b"],
["a","a","b"]
]```

Solution: DFS, Subsets变种题 考虑每个间隙是partition还是不partition

```public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
partitionHelper(s, new ArrayList<String>(), result);
return result;
}

public void partitionHelper(String s, ArrayList<String> curr, List<List<String>> result) {
if (s.length() == 0) {
result.add(new ArrayList<String>(curr));
return;
}
for (int i = 0; i < s.length(); i++) {
String currString = s.substring(0, i + 1);
if (isPalindrome(currString)) {
curr.add(currString);
partitionHelper(s.substring(i + 1), curr, result);
curr.remove(curr.size() - 1); //important
}
}
}

public boolean isPalindrome(String s) {
int start = 0;
int end = s.length() - 1;
while (start <= end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}```
Share