Ok i have this program I have to do for college that gets a word and returns a palindrome for this word.

A palindrome is a word that can be read backwards the same way you read forward. Example: "baab" is a palindrome.

I was proposed to use dynamic programming and a greedy algorithm to solve this.

Example of what the program does: Gets the word "banana" and it has to turn it to a palindrome. Using dynamic programming it has to return an optimal solution. The best solution for "banana" is "bananab" which is a palindrome. Got it?

The dynamic approch was not a problem, im having trouble about the greedy one.

I have thought of this algorithm but im not sure if its a greedy. What you guys think?

- gets the word.
- make a copy of the same word on another string but backwards.
- compare both words.
- if ( they are equal ) return;
- else remove one letter from the beggining of normal word, and one latter from the end of the backwards word.

Repeat that process until the "if" condition is satisfied. Then it will find the last palindrome that exists on the word. It's not optimal, but it works.

The question is? Is that a greedy algorithm?

Thanks guys looking for help!

Figure it out and stop posting this in the d3 forum

since your algorithm doesn't satisfy the prompt, why are you even considering it?

how is optimal defined? if you had bobo for example, is the optimal solution bob (one letter removed) or bobob (one letter added) or boob (one swap)?

have you considered trying the levenshtein distance or something similar?

It does satisfy, but not sure about its greedyness.

You can't remove letters, just add. In this case my algorithm does not add letters in the middle of the word. Just in the and.
You don't have to form the palyndrome, you have to return the number of letters to be isnerted in the string that makes it a palindrome. Does not have to be optimal, or in other words, it doesnt need to return the least number of letters to insert on that word
to make it palindrome. Got it?

This post was edited by Portgas on Nov 8 2012 07:15am

hes posting in the programming section u pothead

n bump sry

This post was edited by xEric on Nov 8 2012 08:15am

yeah lol

as carteblanche says, your algorithm doesn't satisfy the requirement. the output of your algorithm for an input such as "banana" would be "anana" and not "bananab".

he did also post there

http://forums.d2jsp.org/topic.php?t=65127531&f=153

This post was edited by Garciaparra on Nov 8 2012 01:11pm

Just mentioned... I was iso an ice climbers for real.

If it doesn't have to be optimal and you dont have to actually construct it, then what's the point? you can just return length() * 2 - 1, which is the result of appending itself in reverse (minus the last character)

abcd -> abcdcba





wat