CODEWITHSUNDEEP
algorithm
noisy cat
noisy cat

Reputation: 3065

Make palindrome from given word

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.

Upvotes: 2

Views: 1451

Answers (2)

interjay
interjay

Reputation: 110088

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.

Upvotes: 6

Simeon Visser
Simeon Visser

Reputation: 122336

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 abca then the first character is an a and the string also ends with a).
    • 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.

Upvotes: 0

Related Questions