Problem: A string can be partitioned into some substrings, such that each substring is a palindrome. For example, there are a few strategies to split the string “abbab” into palindrome substrings, such as: “abba”|”b”, “a”|”b”|”bab” and “a”|”bb”|”a”|”b”.
Solution 1: Split at any space between two characters
Given a substring of str, starting from the index i and ending at the index j (denoted as str[i:j]), we define a function f(i, j) to denote the minimal number of splits to partition the substring str[i:j] into a set of palindromes. If the substring is a palindrome itself, we don’t have to split so f(i, j) is 0. If the substring is not a palindrome, the substring is split between two characters k and k+1. f(i, j)= f(i,k)+ f(k+1, j)+1 under such conditions. Therefore, f(i, j) can be defined with the following equation:
The value of f(0, n-1) is the value of the minimal number of splits to partition str into palindromes, if n is the length of str.
int minSplit_1(const string& str)
{
int length = str.size();
int* split = new int[length * length];
for(int i = 0; i < length; ++i)
split[i * length + i] = 0;
for(int i = 1; i < length; ++i)
{
for(int j = length - i; j > 0; --j)
{
int row = length - i - j;
int col = row + i;
if(isPalindrome(str, row, col))
{
split[row * length + col] = 0;
}
else
{
int min = 0x7FFFFFFF;
for(int k = row; k < col; ++k)
{
int temp1 = split[row * length + k];
int temp2 = split[(k + 1) * length + col];
if(min > temp1 + temp2 + 1)
min = temp1 + temp2 + 1;
}
split[row * length + col] = min;
}
}
}
int minSplit = split[length - 1];
delete[] split;
return minSplit;
}
Optimization to verify palindromes:
Usually it costs O(n) time to check whether a string with length n is a palindrome.
If we could reduce the cost of isPalindrome to O(1), the time complexity of the second solution would be O(n2).
Notice that the substring str[i,j] is a palindrome only if the characters at index i and j, and str[i+1,j-1] is also a palindrome. We could build a 2D table accordingly to store whether every substring ofstr is a palindrome or not during the preprocessing. With such a table, the function isPalindrome can verify the substring str[i,j] in O(1) time.
Read full article from Coding Interview Questions: No. 43 - Minimal Number of Palindromes on a String