A palindrome is any word or number that is the same backward and forward. For example, 121 is a palindrome; if we reverse this number, we again get the same number, i.e., 121. Similarly, “aba” and “aaa” are palindromes. In this article, we will solve the Palindrome Partitioning problem from leetcode with implementation in various programming languages.
Palindrome Partitioning Problem Explained
In the Palindrome Partitioning problem, we are given a string, and the task is to partition this string in such a way that each partition forms a palindrome.
For example, if the string is “abbaa”, potential partitions include [a, bb, aa], [a, b, b, a, a], [a, bb, a, a], and [a, b, b, aa]. Your goal is to return all possible answers for the given string.
Input: “abx”
Output: [[a, b, x]]
Input: “aaa”
Output: [[aaa], [aa, a], [a, aa], [a, a, a]].
Note: The provided set of arrays, [[a, aa], [a, aa]], is not possible because the first and second arrays are identical.
The naive way to approach this problem is to create all the substrings and check if they are palindrome or not if they are then push them into the answer vector.
For example, Input: “bbaa”, then first create all its substrings
Only 1, 2, 5, and 6 are a palindromic partition of the given string.
Here is a step-by-step approach:
- Partition the given strings into two strings and calculate all their palindrome partition
- Now repeat the above steps to partitions.
- Now check if the given string is palindrome or not if it is then push this string as a vector in our resultant vectors.
- Now, generate all the combinations that can be formed by the two vectors returned by the partitions.
- Now return this vector as the resultant vector.
- Remove all the duplicates from the resultant vector.
The time complexity of the above solution is O((2^n)*(n^3)). Here n is the length of the string. We are recursively partitioning at all the indexes and again repeating the same process for that partition which laid to a time complexity of (2^n). We are also using 3 loops inside this. Two for all the combinations and one for pushing the values into the array.
The space complexity of the above solution is O(k*n) where n is the size of the array. K is the total number of combinations we can make.
Optimized Approach
In the above-mentioned approach, the time complexity is significant, often resulting in Time Limit Exceeded (TLE) errors. To mitigate this issue for Palindrome Partitioning, we can partition the string into two segments and verify whether the left partition is a palindrome. If it is, we proceed to identify all palindrome partitions within the right side.
Let’s examine this approach step by step:
- Iterate over each index and check if we divide the string at this index to see if the left part is palindromic or not.
- If it is palindromic then partition the right side in such a way that all the partitions are palindromic
- While checking whether the string is palindromic or not, store the answer in the array so that next time if the same value occurs then return the answer without checking.
- After finding all the partitions store them in the resultant array.
- Return the array after that.
Let’s examine the code for the above approach.
C++ Code
Here is the C++ program to solve Palindrome Paritioning problem:
#include<bits/stdc++.h>
using namespace std;
bool isPalindrome(string &s, int start, int end, vector<vector<int>>&dp) {
if(dp[start][end]!=-1) return dp[start][end] ? true: false;
while (start < end) {
if (s[start] != s[end]) {
dp[start][end] = 0;
return false;
}
start++;
end--;
}
dp[start][end] = 1;
return true;
}
void solve(int start, string& s,vector<string>¤t, vector<vector<string>>&ans, vector<vector<int>>&dp){
if(start == s.size()){
ans.push_back(current);
return;
}
for(int i=start;i<s.size();i++){
if(isPalindrome(s,start,i,dp)){
current.push_back(s.substr(start, i-start+1));
solve(i+1, s, current, ans, dp);
current.pop_back();
}
}
return;
}
vector<vector<string>> find_palindrome(string& s, vector<vector<int>>& dp){
vector<vector<string>>ans;
vector<string>current;
solve(0,s,current,ans,dp);
return ans;
}
int main(){
string s = "favtutor";
vector<vector<int>>dp(17, vector<int>(17,-1));
vector<vector<string>>res = find_palindrome(s, dp);
for(int i=0;i<res.size();i++){
for(int j=0;j<res[i].size();j++){
cout<<res[i][j]<<", ";
}
cout<<endl;
}
return 0;
}Java Code
We can program it with Java also:
import java.util.ArrayList;
import java.util.List;
class PalindromePartitioning {
static boolean isPalindrome(String s, int start, int end, int[][] dp) {
if (dp[start][end] != -1)
return dp[start][end] == 1;
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
dp[start][end] = 0;
return false;
}
start++;
end--;
}
dp[start][end] = 1;
return true;
}
static void solve(int start, String s, List<String> current, List<List<String>> ans, int[][] dp) {
if (start == s.length()) {
ans.add(new ArrayList<>(current));
return;
}
for (int i = start; i < s.length(); i++) {
if (isPalindrome(s, start, i, dp)) {
current.add(s.substring(start, i + 1));
solve(i + 1, s, current, ans, dp);
current.remove(current.size() - 1);
}
}
return;
}
static List<List<String>> findPalindrome(String s, int[][] dp) {
List<List<String>> ans = new ArrayList<>();
List<String> current = new ArrayList<>();
solve(0, s, current, ans, dp);
return ans;
}
public static void main(String[] args) {
String s = "favtutor";
int[][] dp = new int[17][17];
for (int i = 0; i < 17; i++) {
for (int j = 0; j < 17; j++) {
dp[i][j] = -1;
}
}
List<List<String>> res = findPalindrome(s, dp);
for (List<String> list : res) {
for (String str : list) {
System.out.print(str + ", ");
}
System.out.println();
}
}
}Python Code
Here is the Python solution for Palindrome Partitioning:
def is_palindrome(s, start, end, dp):
if dp[start][end] != -1:
return True if dp[start][end] == 1 else False
while start < end:
if s[start] != s[end]:
dp[start][end] = 0
return False
start += 1
end -= 1
dp[start][end] = 1
return True
def solve(start, s, current, ans, dp):
if start == len(s):
ans.append(current[:])
return
for i in range(start, len(s)):
if is_palindrome(s, start, i, dp):
current.append(s[start:i + 1])
solve(i + 1, s, current, ans, dp)
current.pop()
def find_palindrome(s, dp):
ans = []
current = []
solve(0, s, current, ans, dp)
return ans
if __name__ == "__main__":
s = "favtutor"
dp = [[-1] * 17 for _ in range(17)]
res = find_palindrome(s, dp)
for sublist in res:
print(", ".join(sublist))Output:
f, a, v, t, u, t, o, r
f, a, v, tut, o, rThe time complexity of the above code reduces to O(2^n), as we employ backtracking and memoization in our solution. Additionally, we avoid finding combinations, which eliminates the need for the three loops.
The space complexity will be O(k*n), where k represents the total combinations and n denotes the size of the string.
Here is a comparison of both the approaches:
| Approach | Time Complexity | Space Complexity | Description |
|---|---|---|---|
| Brute Force Approach | O((2^n)(n^3)) | O(k*n) | We are recursively traversing each index and performing the partitioning process. |
| Optimized Approach | O((2^n)) | O(k*n) | We are implementing backtracking while also storing whether the substrings are palindromes or not. |
Conclusion
In the above article, we have seen how we can reduce our time complexity with memoization for the Palindrome Partitioning problem from leetcode. We have also discussed the backtracking approach, which is difficult to understand for students. You can get help from our Data Structures Tutors online to learn it thoroughly.
