Solution of geeksforgeeks problem.
http://practice.geeksforgeeks.org/problems/form-a-palindrome/0
Problem:
Given a string, find the minimum number of characters to be inserted to convert it to palindrome.
For Example:
ab: Number of insertions required is 1. bab or aba
aa: Number of insertions required is 0. aa
abcd: Number of insertions required is 3. dcbabcd
Input:
The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is S.
Output:
Print the minimum number of characters.
Constraints:
1 ≤ T ≤ 50
1 ≤ S ≤ 40
Example:
Input:
3
abcd
aba
geeks
Output:
3
0
3
Solution:
Answer is ( length of the input string - length of LCS(input string, reverse of input string) )
Code:
#include<bits/stdc++.h>
using namespace std;
string str; // input string
string rev; // reverse of the input string
int dp[50][50]; // LCS 2-d array
// return length of LCS between string a and string b
int LCS(string a, string b)
{
memset(dp, 0, sizeof dp);
int a_len = a.length();
int b_len = b.length();
for(int i=1; i<=a_len; i++){
for(int j=1; j<=b_len; j++){
if(a[i-1]==b[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}
else{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[a_len][b_len];
}
void solve()
{
cin>>str;
rev = str;
reverse(rev.begin(), rev.end());
int lcs = LCS(str, rev);
cout<< str.length() - lcs <<endl;
}
int main()
{
ios_base::sync_with_stdio(0);
int t=1; cin>>t;
while(t--){
solve();
}
return 0;
}
Ideone Link:
https://ideone.com/gIRQLc
http://practice.geeksforgeeks.org/problems/form-a-palindrome/0
Problem:
Given a string, find the minimum number of characters to be inserted to convert it to palindrome.
For Example:
ab: Number of insertions required is 1. bab or aba
aa: Number of insertions required is 0. aa
abcd: Number of insertions required is 3. dcbabcd
Input:
The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is S.
Output:
Print the minimum number of characters.
Constraints:
1 ≤ T ≤ 50
1 ≤ S ≤ 40
Example:
Input:
3
abcd
aba
geeks
Output:
3
0
3
Solution:
Answer is ( length of the input string - length of LCS(input string, reverse of input string) )
Code:
#include<bits/stdc++.h>
using namespace std;
string str; // input string
string rev; // reverse of the input string
int dp[50][50]; // LCS 2-d array
// return length of LCS between string a and string b
int LCS(string a, string b)
{
memset(dp, 0, sizeof dp);
int a_len = a.length();
int b_len = b.length();
for(int i=1; i<=a_len; i++){
for(int j=1; j<=b_len; j++){
if(a[i-1]==b[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}
else{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[a_len][b_len];
}
void solve()
{
cin>>str;
rev = str;
reverse(rev.begin(), rev.end());
int lcs = LCS(str, rev);
cout<< str.length() - lcs <<endl;
}
int main()
{
ios_base::sync_with_stdio(0);
int t=1; cin>>t;
while(t--){
solve();
}
return 0;
}
Ideone Link:
https://ideone.com/gIRQLc
No comments:
Post a Comment