Databases
StackOverflow2013
Postsdbo
POHow can I compute the number of characters required to turn a string into a palindrome?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow can I compute the number of characters required to turn a string into a palindrome?
    primarykey
    data
    text
    <p>I recently found a contest problem that asks you to compute the minimum number of characters that must be inserted (anywhere) in a string to turn it into a palindrome.</p> <p>For example, given the string: "abcbd" we can turn it into a palindrome by inserting just two characters: one after "a" and another after "d": "a<b>d</b>bcbd<b>a</b>".</p> <p>This seems to be a generalization of a similar problem that asks for the same thing, except characters can only be added at the end - this has a pretty simple solution in O(N) using hash tables.</p> <p>I have been trying to modify the <a href="http://en.wikipedia.org/wiki/Levenshtein_distance" rel="noreferrer">Levenshtein distance algorithm</a> to solve this problem, but haven't been successful. Any help on how to solve this (it doesn't necessarily have to be efficient, I'm just interested in any DP solution) would be appreciated.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USPete Kirkham
    1. USIVlad
    plurals
    1. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow can I compute the number of characters required to turn a string into a palindrome?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POHow can I compute the number of characters required to turn a string into a palindrome?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHow can I compute the number of characters required to turn a string into a palindrome?
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO@IVlad - excellent question. I've removed the intro bit, and added a link to the Wikipedia article on Levenshtein. Hope that's OK. Welcome to Stack Overflow!
      singulars
      1. POHow can I compute the number of characters required to turn a string into a palindrome?
      1. USDominic Rodger
    2. COI forgot to ask, is this homework?
      singulars
      1. POHow can I compute the number of characters required to turn a string into a palindrome?
      1. This table or related slice is empty.
    3. CONot homework. It was a problem given at a computer science olympiad in my country a few years ago, I was just interested in the solution since I couldn't find an official one nor figure out a DP on my own.
      singulars
      1. POHow can I compute the number of characters required to turn a string into a palindrome?
      1. USIVlad
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload