Problem Statement:
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
Example 1:
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Example 2:
Input: s = "a"
Output: [["a"]]
Constraints:
- 1 <= s.length <= 16
- s contains only lowercase English letters.
Solution:
Algorithm:
- Use DFS to traverse all the possible partitions.
- Use a helper function to check if the current substring is a palindrome.
- If the current substring is a palindrome, add it to the path and continue to traverse the rest of the string.
- If the current substring is not a palindrome, do not add it to the path and continue to traverse the rest of the string.
- If the current index is equal to the length of the string, add the current path to the result.
- After the traversal is completed, return the result.
Code:
public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
List<String> path = new ArrayList<>();
dfs(s, 0, path, res);
return res;
}
private void dfs(String s, int index, List<String> path, List<List<String>> res) {
if (index == s.length()) {
res.add(new ArrayList<>(path));
return;
}
for (int i = index; i < s.length(); i++) {
if (isPalindrome(s, index, i)) {
path.add(s.substring(index, i + 1));
dfs(s, i + 1, path, res);
path.remove(path.size() - 1);
}
}
}
private boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
}
Time Complexity:
O(n*2^n)O(nā2n) The time complexity of the backtracking algorithm is exponential, because in the worst case, we need to add n-1 separators into a string of length n, which results in 2^n2
Space Complexity:
O(n)O(n) The space complexity of the backtracking algorithm is linear, because in the worst case, the depth of the recursion tree can reach nn.
Top comments (0)