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

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

2. Implementation

(1) Backtracking

``````class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
List<String> palindromes = new ArrayList<>();
getPartitions(0, s, palindromes, res);
return res;
}

public void getPartitions(int index, String s, List<String> palindromes, List<List<String>> res) {
if (index == s.length()) {
return;
}

for (int i = index; i < s.length(); i++) {
if (isPalindrome(s, index, i)) {
getPartitions(i + 1, s, palindromes, res);
palindromes.remove(palindromes.size() - 1);
}
}
}

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

3. Time & Space Complexity

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

Last updated