как преобразовать строку в палиндром с минимальным количеством операций? - PullRequest
Новая
       16

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

14 голосов
/ 19 января 2011

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

Например, для ввода mohammadsajjadhossain, вывод будет 8.

Ответы [ 2 ]

9 голосов
/ 19 января 2011

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

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

2 голосов
/ 19 января 2011

Вам просто нужно вычислить ограниченное количество расстояний Левенштейна, по одному на каждую возможную точку поворота палиндрома. Опорная точка может быть буквой или между двумя буквами, поэтому строка длиной 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")
и т. д.

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

...