Author |
Topic: convert to pallindrome (Read 3998 times) |
|
witee
Newbie
Posts: 48
|
 |
convert to pallindrome
« on: Sep 17th, 2010, 5:16am » |
 Quote  Modify
|
given a word,convert it into a pallindrome with minimum addition of letters to it.letters can be added anywhere in the word.for eg if yahoo is given result shud be yahoohay.most optimized solution??
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: convert to pallindrome
« Reply #1 on: Sep 17th, 2010, 5:28am » |
Quote Modify
|
A dynamic programming solution would work. Similar to finding the minimum edit distance of a string with its reverse (but only allowing insertions).
But I doubt that is sufficiently optimized.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: convert to pallindrome
« Reply #2 on: Sep 17th, 2010, 5:09pm » |
Quote Modify
|
1] Find the longest palindromic sub-string of the given string
2] Assuming this longest palindromic sub-string as the core of your final palindrome, scan both left and right of this palindrome and suitably add characters to make the entire string palindromic
I believe that this addition should be optimal.
-- AI
P.S. -> I am trying to see if there is any counter example for the above claim or a proof of the same, if possible.
Found a counter example.
|
| « Last Edit: Sep 18th, 2010, 5:27am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
witee
Newbie
Posts: 48
|
|
Re: convert to pallindrome
« Reply #3 on: Sep 18th, 2010, 6:43am » |
Quote Modify
|
@towr
can u explain with an example say yahoo??
i tried but i am getting wrong answer?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: convert to pallindrome
« Reply #4 on: Sep 18th, 2010, 1:57pm » |
Quote Modify
|
I think in that case the table, with backpointers, would be
$ y a h o o
$ . 1< 2< 3< 4 5
o 1 2 3 4 \4 5
o 2 3 4 5 5 \5
h 3 4 5 5 6 ^6
a 4 5 5 6 7 ^7
y 5 5 6 7 8 ^8
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
witee
Newbie
Posts: 48
|
|
Re: convert to pallindrome
« Reply #5 on: Sep 18th, 2010, 11:53pm » |
Quote Modify
|
@towr
so according to u answer is 8..whereas answer is 4...by adding 0hay in the end..i.e yahooohay...correct me if i am wrong!!!!!!!!!!!!!!
|
| « Last Edit: Sep 18th, 2010, 11:54pm by witee » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: convert to pallindrome
« Reply #6 on: Sep 19th, 2010, 3:39am » |
Quote Modify
|
Your interpretation of the table is wrong: The table gives the resulting string-length, and via the backpointers the extended string. yahoohay is 8 letters long and 3 letters (hay) were added (not 4).
|
| « Last Edit: Sep 19th, 2010, 3:40am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
swami
Newbie
Gender:
Posts: 17
|
|
Re: convert to pallindrome
« Reply #7 on: Sep 21st, 2010, 1:27am » |
Quote Modify
|
@TenaliRaman
Can u post the counter example?
|
|
IP Logged |
|
|
|
hemanshu
Newbie
Gender:
Posts: 14
|
|
Re: convert to pallindrome
« Reply #8 on: Sep 21st, 2010, 11:47am » |
Quote Modify
|
@towr : I am unable to get .. what recursive function be applied to it .. as in the case "cabcbayc" ...just adding 'y' at the second position will make it palindrom .
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: convert to pallindrome
« Reply #9 on: Sep 21st, 2010, 12:19pm » |
Quote Modify
|
Yes, and? That's what my algorithm gives..
$ c a b c b a y c
$ 0 1 2 3 4 5 6 7 8
\
c 1 1 2 3 4 5 6 7 8
|
y 2 2 3 4 5 6 7 7 8
\
a 3 3 3 4 5 6 7 8 9
\
b 4 4 4 4 5 6 7 8 9
\
c 5 5 5 5 5 6 7 8 9
\
b 6 6 6 6 6 6 7 8 9
\
a 7 7 7 7 7 7 7-8 9
\
c 8 8 8 8 8 8 8 9 9
for building the table (minus first column and row) you can use the following python code
Python Code:def palindromize(str):
l = len(str);
t = [[0 for i in range(l)] for j in range(l)];
t[0][0] = 1 if (str[-1] == str[0]) else 2;
for i in range (1,l):
t[0][i] = i+1 if (str[-1] == str[i]) else t[0][i-1] + 1;
for j in range (1,l):
t[j][0] = j+1 if (str[l-j-1] == str[0]) else t[j-1][0] + 1;
for j in range (1,l):
for i in range (1,l):
t[j][i] = min(t[j][i-1],t[j-1][i],t[j-1][i-1])+1 if (str[l-j-1] == str[i]) else min(t[j][i-1],t[j-1][i])+1;
print t;
|
|
And then you just need to do some backtracking to find the completed string.
|
| « Last Edit: Sep 21st, 2010, 12:23pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: convert to pallindrome
« Reply #10 on: Sep 25th, 2010, 2:59am » |
Quote Modify
|
on Sep 21st, 2010, 1:27am, swami wrote:@TenaliRaman
Can u post the counter example? |
|
The counter example is to take a long palindrome and pepper it with random characters
abccba
zabxcxcyba
In this case the longest palindromic substring will be xcx, but if you use that as a core, you will use lot more characters to make the whole string a palindrome.
Instead what you should do is figure out the longest palindromic subsequence which will be abccba and then use that as a core to make the entire string a palindrome. However, this is O(n^2) so we don't gain anything more than what towr achieves with his method (plus his method does it more efficiently).
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: convert to pallindrome
« Reply #11 on: Sep 29th, 2010, 5:56am » |
Quote Modify
|
on Sep 21st, 2010, 12:19pm, towr wrote:Yes, and? That's what my algorithm gives..
$ c a b c b a y c
$ 0 1 2 3 4 5 6 7 8
\
c 1 1 2 3 4 5 6 7 8
|
y 2 2 3 4 5 6 7 7 8
\
a 3 3 3 4 5 6 7 8 9
\
b 4 4 4 4 5 6 7 8 9
\
c 5 5 5 5 5 6 7 8 9
\
b 6 6 6 6 6 6 7 8 9
\
a 7 7 7 7 7 7 7-8 9
\
c 8 8 8 8 8 8 8 9 9
|
|
i am enable to understand your approach here. Are you trying to calculate the steps required to convert "c a b c b a y c" to "c y a b c b a c"
and Why matrix[c,c] is 1, since 0 steps are required to convert a c into c ?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: convert to pallindrome
« Reply #12 on: Sep 29th, 2010, 8:43am » |
Quote Modify
|
Have you read what this topic is about? What would be the point of converting a string to it's reverse in finding a palindrome?
What we're trying to do is merge the string and its reverse in the most efficient way possible. So, at point i,j in the matrix you have a string that has most effectively merged the first i characters of the string and the first j characters of the reverse string, totaling a string of length M[i,j].
|
| « Last Edit: Sep 29th, 2010, 8:55am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: convert to pallindrome
« Reply #13 on: Oct 3rd, 2010, 11:25pm » |
Quote Modify
|
@towr
got it! thanks 
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: convert to pallindrome
« Reply #14 on: Jan 27th, 2011, 11:04pm » |
Quote Modify
|
I think we can do it even without maintaing a matrix in O(n^2). All we have to find is the length of the non-overlapping subsequence of a string and its reverse.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
kaka
Newbie
Gender:
Posts: 24
|
|
Re: convert to pallindrome
« Reply #15 on: Dec 9th, 2011, 8:56am » |
Quote Modify
|
For a string of length n, find the longest palindrome which is a prefix of the reversed string (or suffix of the original string), say it is of length k. Now reverse the first n-k characters and append to the original string.
Ex: Yahoo , Longest palindrome of oohay is oo, so append haY to Yahoo.
Any counter example? Just wanted to confirm my solution.
|
| « Last Edit: Dec 9th, 2011, 8:59am by kaka » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: convert to pallindrome
« Reply #16 on: Dec 9th, 2011, 11:57am » |
Quote Modify
|
Try "ahba"
Your approach would give "ahbabha", whereas "ahbha" and "abhba" are shorter palindromes.
|
| « Last Edit: Dec 9th, 2011, 11:58am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
kaka
Newbie
Gender:
Posts: 24
|
|
Re: convert to pallindrome
« Reply #17 on: Dec 9th, 2011, 5:11pm » |
Quote Modify
|
Missed the part 'letters can be added any where in the word'. Thanks Towr
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print