MinInsert-Palindrome Problem
Difficulty : Medium
You are given a string of characters, or numbers. Find the minimum number of characters to be inserted into the string in order to obtain a palindrome.
A palindrome is a word, phrase, number, or other sequence of symbols or elements that reads the same forward or reversed.
For example, the string abcbd can be transformed into a palindrome ("dabcbad" or "adbcbda"). However, inserting fewer than 2 characters will not produce a palindrome.
Input Format:
First line contains an integer 'n' specifying the length of the string, where 3<=n<=20
Second line contains a string of length n.
Note: Upper-case and lower-case characters are considered as different. Elements of the string are either English alphabets or numerals.
Output Format
One line containing the minimum number of insertions required to make the string a palindrome
Input code:
// A Naive recursive program to find minimum number insertions
// needed to make a string palindrome
#include <stdio.h>
#include <limits.h>
#include <string.h>
// A utility function to find minimum of two numbers
int min(int a, int b)
{ return a < b ? a : b; }
// Recursive function to find minimum number of insersions
int findMinInsertions(char str[], int l, int h)
{
// Base Cases
if (l > h) return INT_MAX;
if (l == h) return 0;
if (l == h - 1) return (str[l] == str[h])? 0 : 1;
// Check if the first and last characters are same. On the basis of the
// comparison result, decide which subrpoblem(s) to call
return (str[l] == str[h])? findMinInsertions(str, l + 1, h - 1):
(min(findMinInsertions(str, l, h - 1),
findMinInsertions(str, l + 1, h)) + 1);
}
// Driver program to test above functions
int main()
{int n,i;
char str[100000];
scanf("%d",&n);
/* for(i=0;i<n;i++)
{
scanf("%c",str[i]);
}str[i]='\0';*/
scanf("%s",str);
printf("%d\n", findMinInsertions(str, 0, strlen(str)-1));
return 0;
}
Source Code 2:
#include<stdio.h>
int a[10005],b[10005];
int main()
{
int n,i,l,d1,d2,k;
char ch,c[5001];
scanf("%d",&n);
ch=getchar();
while(ch==' ' || ch=='\n' || ch=='\t')
{
ch=getchar();
}
for(i=0;i<n;i++)
{
c[i]=ch;
ch=getchar();
}
for(i=0;i<2*n-1;i++)
a[i]=0;
k=2*n-1;
for(l=1;l<n;l++)
{
for(i=0;i<n-l;i++)
{
d1=12345;
if(c[i]==c[i+l])
{
b[2*i]=a[2*i+1];
}
else
{
d1=a[2*i]+1;
d2=a[2*i+2]+1;
b[2*i]=d1<d2?d1:d2;
}
}
k-=2;
for(i=0;i<k;i=i+2)
{
a[i+1]=a[i+2];
a[i]=b[i];
//printf("%d %d ",a[i],a[i+1]);
}
//printf("\n");
//for(i=0;i<k;i++)
// printf("%d ",a[i]);
//printf("\n");
}
printf("%d\n",a[0]);
return 0;
}