Palindrome Partitioning
Given a string s, partition s into all and saidQuestion substrings at each step. Return all possible palindrome partitions of s.
Constraints:
- 1 <= s.length <= 16
- s contains only lowercase English letters
Examples:
Input: "aab"
Output: [["a","a","b"],["aa","b"]]
Explanation: Explanation: There are two possible palindrome partitions of "aab": ["a","a","b"] and ["aa","b"]
Solutions
Backtracking
Time: O(2^n * n)Space: O(n)
The solution uses a backtracking approach to generate all possible palindrome partitions of the input string. It checks each substring to see if it is a palindrome and if so, adds it to the current path and recursively calls the backtrack function with the remaining substring.
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
backtrack(res, new ArrayList<>(), s, 0);
return res;
}
private void backtrack(List<List<String>> res, List<String> tempList, String s, int start) {
if (start == s.length()) {
res.add(new ArrayList<>(tempList));
}
else {
for (int i = start;
i < s.length();
i++) {
if (isPalindrome(s, start, i)) {
tempList.add(s.substring(start, i + 1));
backtrack(res, tempList, s, i + 1);
tempList.remove(tempList.size() - 1);
}
}
}
}
private boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left++) != s.charAt(right--)) {
return false;
}
}
return true;
}Follow-up:
How would you optimize the solution to handle very large input strings?
