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.
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> path;
backtrack(res, path, s, 0);
return res;
}
void backtrack(vector<vector<string>>& res, vector<string>& path, string& s, int start) {
if (start == s.size()) {
res.push_back(path);
return;
}
for (int i = start;
i < s.size();
i++) {
if (isPalindrome(s, start, i)) {
path.push_back(s.substr(start, i - start + 1));
backtrack(res, path, s, i + 1);
path.pop_back();
}
}
}
bool isPalindrome(string& s, int left, int right) {
while (left < right) {
if (s[left++] != s[right--]) {
return false;
}
}
return true;
}
}
;Follow-up:
How would you optimize the solution to handle very large input strings?
