wu :: forums
« wu :: forums - convert to pallindrome »

Welcome, Guest. Please Login or Register.
Oct 31st, 2024, 4:45pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: SMQ, ThudnBlunder, Grimbal, william wu, Eigenray, Icarus, towr)
   convert to pallindrome
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: convert to pallindrome  (Read 4002 times)
witee
Newbie
*





   
Email

Posts: 48
convert to pallindrome  
« on: Sep 17th, 2010, 5:16am »
Quote Quote Modify 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: male
Posts: 13730
Re: convert to pallindrome  
« Reply #1 on: Sep 17th, 2010, 5:28am »
Quote Quote Modify 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: male
Posts: 1001
Re: convert to pallindrome  
« Reply #2 on: Sep 17th, 2010, 5:09pm »
Quote Quote Modify 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
*





   
Email

Posts: 48
Re: convert to pallindrome  
« Reply #3 on: Sep 18th, 2010, 6:43am »
Quote Quote Modify 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: male
Posts: 13730
Re: convert to pallindrome  
« Reply #4 on: Sep 18th, 2010, 1:57pm »
Quote Quote Modify 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
*





   
Email

Posts: 48
Re: convert to pallindrome  
« Reply #5 on: Sep 18th, 2010, 11:53pm »
Quote Quote Modify 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: male
Posts: 13730
Re: convert to pallindrome  
« Reply #6 on: Sep 19th, 2010, 3:39am »
Quote Quote Modify 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
*





   
Email

Gender: male
Posts: 17
Re: convert to pallindrome  
« Reply #7 on: Sep 21st, 2010, 1:27am »
Quote Quote Modify Modify

@TenaliRaman
 
Can u post the counter example?
IP Logged
hemanshu
Newbie
*





   


Gender: male
Posts: 14
Re: convert to pallindrome  
« Reply #8 on: Sep 21st, 2010, 11:47am »
Quote Quote Modify 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: male
Posts: 13730
Re: convert to pallindrome  
« Reply #9 on: Sep 21st, 2010, 12:19pm »
Quote Quote Modify 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: male
Posts: 1001
Re: convert to pallindrome  
« Reply #10 on: Sep 25th, 2010, 2:59am »
Quote Quote Modify 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: male
Posts: 250
Re: convert to pallindrome  
« Reply #11 on: Sep 29th, 2010, 5:56am »
Quote Quote Modify 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: male
Posts: 13730
Re: convert to pallindrome  
« Reply #12 on: Sep 29th, 2010, 8:43am »
Quote Quote Modify 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: male
Posts: 250
Re: convert to pallindrome  
« Reply #13 on: Oct 3rd, 2010, 11:25pm »
Quote Quote Modify Modify

@towr
 
got it! thanks Smiley
IP Logged

The only thing we have to fear is fear itself!
birbal
Full Member
***





   


Gender: male
Posts: 250
Re: convert to pallindrome  
« Reply #14 on: Jan 27th, 2011, 11:04pm »
Quote Quote Modify 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: male
Posts: 24
Re: convert to pallindrome  
« Reply #15 on: Dec 9th, 2011, 8:56am »
Quote Quote Modify 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: male
Posts: 13730
Re: convert to pallindrome  
« Reply #16 on: Dec 9th, 2011, 11:57am »
Quote Quote Modify 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: male
Posts: 24
Re: convert to pallindrome  
« Reply #17 on: Dec 9th, 2011, 5:11pm »
Quote Quote Modify Modify

Missed the part 'letters can be added any where in the word'. Thanks Towr
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board