This is an interview question: "You're given a string, and you want to split it into as few strings as possible such that each string is a palindrome". (I guess a one char string is considered a palindrome, i.e. "abc" is split into "a", "b", "c".)
How would you answer it?
First find all the palindromes in the string such that L[i][j] represents the length of j-th longest palindrome that ends at S[i]. Lets say S is the input string. This could be done in O(N^2) time by first considering length1 palindromes then then length 2 palindromes and so on. Finding Length i palindromes after you know all length i-2 palindromes is the matter of a single character comparison.
This is a dynamic programming problem after that. Let A[i] represent the smallest number of palindrome that Substring(S,0,i-1) can be decomposed into.
A[i+1] = min_{0 <= j < length(L[i])} A[i - L[i][j]] + 1;
Edit based on Micron's request: Here is the idea behind comuting L[i][j]. I just wrote this up to convey the idea, the code may have problems.
// Every single char is palindrome so L[i][0] = 1;
vector<vector<int> > L(S.length(), vector<int>(1,1));
for (i = 0; i < S.length(); i++) {
for (j = 2; j < S.length; j++) {
if (i - j + 1 >= 0 && S[i] == S[i-j + 1]) {
// See if there was a palindrome of length j - 2 ending at S[i-1]
bool inner_palindrome = false;
if (j ==2) {
inner_palindrome = true;
} else {
int k = L[i-1].length;
if (L[i-1][k-1] == j-2 || (k >= 2 && L[i-1][k-2] == j-2)) {
inner_palindrome = true;
}
}
if (inner_palindrome) {
L[i].push_back(j);
}
}
}
}
You can do this in O(n^2) time using Rabin-Karp fingerprinting to preprocess the string to find all of the palindromes in O(n^2) time. After the preprocessing, you run code similar to the following:
np(string s) {
int a[s.size() + 1];
a[s.size()] = 0;
for (int i = s.size() - 1; i >= 0; i--) {
a[i] = s.size() - i;
for (int j = i + 1; j <= s.size(); j++) {
if (is_palindrome(substr(s, i, j))) // test costs O(1) after preprocessing
a[i] = min(a[i], 1 + a[j]);
}
return a[0];
}
bool ispalindrome(string inp)
{
if(inp == "" || inp.length() == 1)
{
return true;
}
string rev = inp;
reverse(rev.begin(), rev.end());
return (rev == inp);
}
int minsplit_count(string inp)
{
if(ispalindrome(inp))
{
return 0;
}
int count= inp.length();
for(int i = 1; i < inp.length(); i++)
{
count = min(count,
minsplit_count(inp.substr(0, i)) +
minsplit_count(inp.substr(i, inp.size() - i)) +
1);
}
return count;
}
An equivalent problem is that of computing the Snip number of a string.
Suppose you wanted to cut a string using the fewest number of snips, so that each remaining piece was itself a palindrome. The number of such cuts we will call the Snip Number of a string. That is the snip number is always equal to one less than the smallest number of palindromes within a given string. Every string of length n has snip number at most n-1, and each palindrome has snip number 0. Here is working python code.
def snip_number(str):
n=len(str)
#initialize Opt Table
# Opt[i,j] = min number of snips in the substring str[i...j]
Opt=[[0 for i in range(n)] for j in range(n) ]
#Opt of single char is 0
for i in range(n):
Opt[i][i] = 0
#Opt for adjacent chars is 1 if different, 0 otherwise
for i in range(n-1):
Opt[i][i+1]= 1 if str[i]!=str[i+1] else 0
# we now define sil as (s)substring (i)interval (l) length of the
# interval [i,j] --- sil=(j-i +1) and j = i+sil-1
# we compute Opt table entry for each sil length and
# starting index i
for sil in range(3, n+1):
for i in range(n-sil+1):
j = i+sil-1
if (str[i] == str[j] and Opt[i+1][j-1]==0):
Opt[i][j] = 0
else:
snip= min( [(Opt[i][t]+ Opt[t+1][j] + 1 ) for t in range(i,j-1)])
Opt[i][j] = snip
return Opt[0][len(str)-1]
#end function snip_number()
mystr=[""for i in range(4)]
mystr[0]="abc"
mystr[1]="ohiho"
mystr[2]="cabacdbabdc"
mystr[3]="amanaplanacanalpanama aibohphobia "
for i in range(4):
print mystr[i], "has snip number:", snip_number(mystr[i])
# abc has snip number: 2
# ohiho has snip number: 0
# cabacdbabdc has snip number: 2
# amanaplanacanalpanama aibohphobia has snip number: 1
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With