I have given word like abca. I want to know how many letters do I need to add to make it palindrome.
In this case its 1, because if I add b, I get abcba.
-
3Sounds like a homework problem ;-) Write out a few examples on paper and think about it. Hint: Take words that you know how many more letters need to be added, and try to inductively extrapolate how you can calculate it in the general case. So look at a word that needs 1, then look at a word that needs 2, then look at a word that needs 3, etc. until you see a pattern. Surely the human mind is capable of some pattern matching; why I could swear that there are at least millions of neurons in your head. Use them!allquixotic– allquixotic2012-07-11 14:05:08 +00:00Commented Jul 11, 2012 at 14:05
-
look on a tag :) and thanks for help :)noisy cat– noisy cat2012-07-11 14:06:25 +00:00Commented Jul 11, 2012 at 14:06
-
1Do you want to find out the FEWEST number of letters to add? Because you can always just append the reverse of the string and have a palindrome.Dan W– Dan W2012-07-11 14:19:09 +00:00Commented Jul 11, 2012 at 14:19
-
@Dan W I want fewest. thats th problem :/noisy cat– noisy cat2012-07-11 14:21:02 +00:00Commented Jul 11, 2012 at 14:21
-
can you re-arrange the letters?Sam I am says Reinstate Monica– Sam I am says Reinstate Monica2012-07-11 14:36:00 +00:00Commented Jul 11, 2012 at 14:36
Add a comment
|
2 Answers
First, let's consider an inefficient recursive solution:
Suppose the string is of the form aSb, where a and b are letters and S is a substring.
If a==b, then f(aSb) = f(S).
If a!=b, then you need to add a letter: either add an a at the end, or add a b in the front. We need to try both and see which is better. So in this case, f(aSb) = 1 + min(f(aS), f(Sb)).
This can be implemented with a recursive function which will take exponential time to run.
To improve performance, note that this function will only be called with substrings of the original string. There are only O(n^2) such substrings. So by memoizing the results of this function, we reduce the time taken to O(n^2), at the cost of O(n^2) space.
Comments
The basic algorithm would look like this:
- Iterate over the half the string and check if a character exists at the appropriate position at the other end (i.e., if you have
abcathen the first character is anaand the string also ends witha).- If they match, then proceed to the next character.
- If they don't match, then note that a character needs to be added.
Note that you can only move backwords from the end when the characters match. For example, if the string is abcdeffeda then the outer characters match. We then need to consider bcdeffed. The outer characters don't match so a b needs to be added. But we don't want to continue with cdeffe (i.e., removing/ignoring both outer characters), we simply remove b and continue with looking at cdeffed. Similarly for c and this means our algorithm returns 2 string modifications and not more.
3 Comments
interjay
This has the same issue as user1168577's answer: when you have the string
bcdeffed, you don't know whether to add b at the end or d at the start. If you just decide to add b you won't necessarily get the best answer.
Simeon Visser
@interjay: Hmm, we could introduce backtracking to search for the minimal number of modifications. So whenever a character needs to be added, add either
b or d and continue your search. When you're done, look at all possible answers that you've found and return the one with the least number of modifications.
amit
backtracking will make the solution exponential in time, which is suboptimal unless the problem is NP-Hard.. [to be honest, I am clueless if it is NP-Hard or not... I have no intuition regarding this one]