how to convert a string into a palindrome with min

问题:

Here is the problem states to convert a string into a palindrome with minimum number of operations. I know it is similar to the Levenshtein distance but I can't solve it yet

For example, for input mohammadsajjadhossain, the output is 8.

回答1:

Perform Levenshtein distance on the string and its reverse. The solution will be the minimum of the operations in the diagonal of the DP array going from bottom-left to top-right, as well as each entry just above and just below the diagonal.

This works because the entries along the diagonal represent the minimum edits required to make the first i and last N-i characters of the string equal and the entries just above and just below represent the minimum for strings ending up with odd-length where the middle (left-over) character doesn't match against anything.

回答2:

You just need to compute a limited number of Levenshtein distances, one for each possible palindrome pivot point. A pivot point can be a letter or it can be between two letters, so a string of length n has 2n-1 pivot points. For each pivot point, you calculate the Levenshtein distance of the characters before the pivot point and the reverse of the characters after it:

(m)ohammadsajjadhossain: Levensthein("", "niassohdajjasdammaho")
m ohammadsajjadhossain: Levensthein("m", "niassohdajjasdammaho")
m(o)hammadsajjadhossain: Levensthein("m", "niassohdajjasdammah")
mo hammadsajjadhossain: Levensthein("mo", "niassohdajjasdammah")
mo(h)ammadsajjadhossain: Levensthein("mo", "niassohdajjasdamma")
moh ammadsajjadhossain: Levensthein("moh", "niassohdajjasdamma")
etc.

Now just take the minimum of these distances. If speed is important, you can optimise away many of these calls.