Как преобразовать строку в палиндром с минимальным количеством операций?

Ответ 1

Выполните расстояние Левенштейна на струне и ее обратном. Решение будет минимальным для операций в диагонали массива DP, идущих с нижнего левого на верхний правый, а также на каждую запись чуть выше и чуть ниже диагонали.

Это работает, потому что записи по диагонали представляют минимальные изменения, необходимые для того, чтобы первый и последний Ni-символы строки были равны, а записи чуть выше и чуть ниже представляли минимум для строк, заканчивающихся нечетной длиной, где средний (слева) символ не совпадает ни с чем.

Ответ 2

Вам просто нужно вычислить ограниченное число Левенштейн расстояний, по одному для каждой возможной точки палиндром поворота. Точка опоры может быть буквой или может быть между двумя буквами, поэтому строка длины n имеет 2n-1 опорные точки. Для каждой точки поворота вы вычисляете расстояние Левенштейна символов до точки поворота и обратную сторону символов после него:

(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")
и т.д.

Теперь просто возьмите минимум этих расстояний. Если скорость важна, вы можете оптимизировать многие из этих вызовов.