hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Palindrome Partitioning


  • Approach:

    1. The problem is said to split the whole string into at most N parts, where each of the parts will be a palindrome. Here, N = length of the string.

    2. Check the image on the right side.

    3. For any given string, we will move forward by processing one index at once.

    4. If the substring till the current index is a palindrome, then we will put them into the partitioned list.

    5. And then we will look for the palindrome substring from the next of the current index.

    6. Once we reach the end of the string, then we will insert the partitioned list into the resultant list.

    7. Then we will return the resultant list.

    8. For example, we have a string "abab".

    9. We will be starting from 0. For length = 1, we check if the substring at index = 0 is a palindrome. We insert them into the partition. And we said index = 1 (index+1), to find out the palindromic substrings.

      • From index = 0, we will look for the palindromic substrings for the length = 2, 3, 4 also.

    10. From index = 1, for length = 1, we check if the substring at index = 1 is a palindrome. We insert them into the partition. And we said index = 2 (index+1), to find out the palindromic substrings.

      • From index = 1, we will look for the palindromic substrings for the length = 2, 3 also.

    11. From index = 2, for length = 1, we check if the substring at index = 2 is a palindrome. We insert them into the partition. And we said index = 3 (index+1), to find out the palindromic substrings.

      • From index = 2, we will look for the palindromic substrings for the length = 2 also.

    12. From index = 3, for length = 1, we check if the substring at index = 3 is a palindrome. We insert them into the partition. And we said index = 4 (index+1), to find out the palindromic substrings.

    13. As the index becomes equal to the length of the string, we insert the partition into the answerList.

    14. Returned the answerList.


  • Time and Space Complexity:

      • Time Complexity: O(N*2^N)

      • Space Complexity: O(N)


Code [C++]

class Solution {

public:


bool isPalindrome(string & s, int start, int end){

int last = end;

for(int i=start; i < last; i++){

if(s[i] != s[last]) return false;

last--;

}

return true;

}


void solve(int pos, string & s, vector<string> & partition, vector<vector<string>>& ans, int n){

if(pos == n){

ans.push_back(partition);

return;

}

for(int i=pos; i<n; i++){

if(isPalindrome(s, pos, i)){

partition.push_back(s.substr(pos, i-pos+1));

solve(i+1, s, partition, ans, n);

partition.pop_back();

}

}

}


vector<vector<string>> partition(string s) {

vector<string>partition;

vector<vector<string>>ans;

int n = s.size();

solve(0, s, partition, ans, n);

return ans;

}

};