131 Palindrome Partitioning

1. Question

Given a strings, partitionssuch that every substring of the partition is a palindrome.
Return all possible palindrome partitioning ofs.
For example, givens="aab", Return
1
[
2
["aa","b"],
3
["a","a","b"]
4
]
Copied!

2. Implementation

(1) Backtracking
1
class Solution {
2
public List<List<String>> partition(String s) {
3
List<List<String>> res = new ArrayList<>();
4
List<String> palindromes = new ArrayList<>();
5
getPartitions(0, s, palindromes, res);
6
return res;
7
}
8
9
public void getPartitions(int index, String s, List<String> palindromes, List<List<String>> res) {
10
if (index == s.length()) {
11
res.add(new ArrayList<>(palindromes));
12
return;
13
}
14
15
for (int i = index; i < s.length(); i++) {
16
if (isPalindrome(s, index, i)) {
17
palindromes.add(s.substring(index, i + 1));
18
getPartitions(i + 1, s, palindromes, res);
19
palindromes.remove(palindromes.size() - 1);
20
}
21
}
22
}
23
24
public boolean isPalindrome(String s, int start, int end) {
25
while (start < end) {
26
if (s.charAt(start) != s.charAt(end)) {
27
return false;
28
}
29
++start;
30
--end;
31
}
32
return true;
33
}
34
}
Copied!

3. Time & Space Complexity

Backtracking: 时间复杂度O(n * 2^n), 空间复杂度O(2^n)