Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
A palindrome string is a string that reads the same backward as forward.
Example 1:
Input: s = "aab" Output: [["a","a","b"],["aa","b"]]
Example 2:
Input: s = "a" Output: [["a"]]
Constraints:
1 <= s.length <= 16scontains only lowercase English letters.
Companies:
Amazon, Google, tiktok, ByteDance
Related Topics:
String, Dynamic Programming, Backtracking
Similar Questions:
In the worst case, s has all the same characters. If s is of length N, then there are 2^(N-1) ways to partition it. For each partition, we also need to copy the strings over and testing if all its segments are palindromes, taking O(N) time. So overall the time complexity is O(N * 2^N).
// OJ: https://leetcode.com/problems/palindrome-partitioning/
// Author: github.com/lzl124631x
// Time: O(N * 2^N)
// Space: O(N) extra space
class Solution {
vector<vector<string>> ans;
vector<string> tmp;
bool isPalindrome(string &s, int i, int j) {
while (i < j && s[i] == s[j]) ++i, --j;
return i >= j;
}
void dfs(string &s, int start) {
if (start == s.size()) {
ans.push_back(tmp);
return;
}
for (int i = start; i < s.size(); ++i) {
if (!isPalindrome(s, start, i)) continue;
tmp.push_back(s.substr(start, i - start + 1));
dfs(s, i + 1);
tmp.pop_back();
}
}
public:
vector<vector<string>> partition(string s) {
dfs(s, 0);
return ans;
}
};We called isPalindrome to the same segment multiple times in Solution 1. We can precompute isPalindrome via DP taking O(N^2) time.
Since we still need to copy the strings over, there is still an O(N) time complexity for each partition.
// OJ: https://leetcode.com/problems/palindrome-partitioning/
// Author: github.com/lzl124631x
// Time: O(N * 2^N)
// Space: O(N)
class Solution {
public:
vector<vector<string>> partition(string s) {
int N = s.size();
vector<vector<bool>> dp(N, vector<bool>(N));
vector<string> tmp;
vector<vector<string>> ans;
function<void(int)> dfs = [&](int i) {
if (i == N) {
ans.push_back(tmp);
return;
}
for (int j = i; j < N; ++j) {
if (!dp[i][j]) continue;
tmp.push_back(s.substr(i, j - i + 1));
dfs(j + 1);
tmp.pop_back();
}
};
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= i; ++j) {
dp[j][i] = s[j] == s[i] && (i - j < 2 || dp[j + 1][i - 1]);
}
}
dfs(0);
return ans;
}
};