Вопрос по java, algorithm, palindrome, string – Создать палиндром из существующей строки, удалив символы

4

Как определить длину самого длинного палиндрома, который вы можете получить из слова, удалив ноль или более букв.

например: amanQQQapl12345anacaZZZnalpaXXXna67890ma
самый длинный палиндром будет состоять из 21 цифры.

Обратите внимание, что если вы будете гуглить, вы найдете алгоритмы для самого длинного палиндромного сабвуфера.sequence и самый длинный палиндромный сабstring, Ваш вопрос является субsequence версия. Li-aung Yip
я еще ничего не пробовал ... нужна помощь с логикой ... Nitin Kabra
возможный дубликатhow to find longest palindromic subsequence? Li-aung Yip
Пожалуйста, отметьте это как алгоритм. Вы получите более быстрые ответы. Hindol

Ваш Ответ

4   ответа
0

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

int d[1000][1000] = {0}; // To store result of previous computation

int computeMaxPalindromeLength(vector<int>& a, int start, int end) {
    if(d[start][end] != 0) // If not precomputed, recompute.
        return d[start][end];
    if(start == end) { // The mid character should be taken as 
        d[start][end] = 1;
        return 1;
    }
    else if(start == end-1) {
        d[start][end] = (a[start] == a[end])?2:1;
        return d[start][end];
    }
    if(a[start] == a[end]) {
        d[start][end] = max( 2 + computeMaxPalindromeLength(a, start+1, end-1), 
            max(computeMaxPalindromeLength(a, start+1, end), computeMaxPalindromeLength(a, start, end-1)));
    } else {
        d[start][end] = max(computeMaxPalindromeLength(a, start+1, end), computeMaxPalindromeLength(a, start, end-1));
    }
    return d[start][end];
}

Вызовите вышеуказанный метод как: -

vector<int>& a; // Convert each character of string to digit if working with alphanumeric characters.
int maxPalindromeLength = computeMaxPalindromeLength(a, 0, a.size()-1);
3

самая длинная общая подпоследовательность W и его зеркало.

Вы можете вычислить его за время O (n & # xB2;) и пространство O (n), где n - это длина W, но если вы знаете, что вам нужно всего лишь удалить несколько символов, чтобы сделать палиндром, вы можете иметь большую сложность.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
8

d[i, j] как длина самого длинного палиндрома в исходной строке.

If s[i] = s[j], d[i, j] = max(d[i+1, j-1] + 2, d[i, j-1], d[i+1, j]).

Otherwise d[i, j] = max(d[i, j-1], d[i+1, j]).

Error: User Rate Limit Exceeded
1

то есть средней буквы, и любое количество четных букв.

Вы можете посчитать частоту каждой буквы. Если это не все или ничего для каждой буквы, добавьте count / 2 * 2 для каждой буквы и добавьте один, если любая буква имеет нечетное число.

Похожие вопросы