Как я могу вычислить количество символов, требуемых превратить строку в палиндром?
Я недавно нашел проблему конкурса, которая просит, чтобы Вы вычислили минимальное количество символов, которые должны быть вставлены (где угодно) в строке для превращения его в палиндром.
Например, учитывая строку: "abcbd" мы можем превратить его в палиндром путем вставки всего двух символов: один после "a" и другой после "d": "adbcbda".
Это, кажется, обобщение подобной проблемы, которая просит то же самое, кроме символов может только быть добавлен в конце - это имеет довольно простое решение в O (N) использование хеш-таблиц.
Я пытался изменить алгоритм расстояния Левенштейна для решения этой проблемы, но не был успешен. Любая справка о том, как решить это (это должно не обязательно быть эффективно, я просто интересуюсь любым решением DP), ценился бы.
1 ответ
Примечание: это просто любопытство. Дэв предложил алгоритм, который можно преобразовать в алгоритм DP, чтобы он мог легко работать за время O (n ^ 2) и пространство O (n ^ 2) (и, возможно, за O (n) при лучшем учете).
Конечно, этот «наивный» алгоритм может действительно пригодиться, если вы решите изменить разрешенные операции.
Вот «наивный» алгоритм, который, вероятно, можно ускорить с помощью умной бухгалтерии.
Для данной строки мы угадываем середину результирующего палиндрома, а затем пытаемся вычислить количество вставок, необходимых для превращения строки в палиндром вокруг этой середины.
Если строка имеет длину n, существует 2n + 1 возможных середин (каждый символ между двумя символами, непосредственно перед и сразу после строки).
Предположим, мы рассматриваем середину, которая дает нам две строки L и R (одну слева и одну справа).
Если мы используем вставки, я считаю, что алгоритм Самая длинная общая подпоследовательность (который является алгоритмом DP) теперь можно использовать для создания «супер» строки, которая содержит как L, так и обратную R, см. Кратчайшая общая суперпоследовательность .
Выберите середину, которая дает вам наименьшее количество вставок.
Думаю, это O (n ^ 3). (Примечание: я не пытался доказать, что это правда).