Palindrome partitioning is a important problem which has a dynamic programming solution. It is a famous problem asked in many interviews. Here we provide C++ solution with an explanation.
Palindrome Partitioning Problem Description
Given a string, we have to determine minimum cuts we need to make such that the sub-strings obtained after cutting the original string form a palindrome.
- Single line input containing input string.
- Single integer the required number of cuts.
- Sub strings are aa, bb, cc.
Palindrome Partitioning Problem Solution
Memoization or Top Down Solution
To build a top down solution we must follow the following steps –
- Break Down the Problem – In this step we try to break down the problem into smaller problems and assume recursion will solve the smaller problems.F(i,j) = Min no. of cuts made in the string (from i to j) such that all sub strings all palindromes. To get the value of F(i,j) we need to divide string from i to j into two parts and recursively find minimum cuts for them.
- Find the base case – Base case is easy in this problem. One base case is if we have a string of length 1 (ie i==j) then we simple return 0 as it is a palindrome of length 1. If we reach an invalid sequence (i>j) , then also we simple return 0. The other base case is if the current string is itself a palindrome, then no need to cut it.
- Check for optimal substructure and overlapping sub problems – It is easy to see that the problem can be broken down into smaller problems. The optimal substructure and overlapping sub problems properties can be visualized below.
Bottom Up Solution
In this approach we solve smaller problems first instead of shoving for bigger problems.We create a table cuts[n][n] (n = string length).
Using similar transitions as above we can get our answer.