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.
var partition = function (s) {
const res = [];
const isPalindrome = (str) => str === str.split('').reverse().join('');
const backtrack = (start, path) => {
if (start === s.length) return res.push(path);
for (let i = start; i < s.length; i++) {
const substr = s.substring(start, i + 1);
if (isPalindrome(substr)) backtrack(i + 1, [...path, substr]);
}
};
backtrack(0, []);
return res;
};
Follow-up:
How would you optimize the solution to handle very large input strings?
