самая длинная палиндромная подстрока с использованием lcs?

Я решал эту проблему с самой длинной палиндромной подстрокой на leetcode и следил за динамическим подход к программированию путем создания одной логической таблицы n * n (которая, я думаю, также является стандартным решением для этого) и успешно ее решил, но мне просто интересно, можно ли решить эту проблему, используя технику, которую мы используем для определения самой длинной общей подпоследовательности или Чтобы быть более точным, просто хочу знать, является ли проблема LCS родительским вопросом этой проблемы, как и в случае самой длинной палиндромной подпоследовательности, которую можно легко решить с помощью LCS, взяв одну другую строку как обратную исходной строке.

Я поискал в Интернете, но не нашел решения с использованием техники LCS, поэтому подумал об этом здесь. Если возможно решить с помощью метода LCS, просьба указать подход или еще какую-нибудь вескую причину, по которой его нельзя решить с помощью LCS.


lcs palindrome longest-substring
person NITESH SHARMA    schedule 30.10.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Я действительно решил эту проблему именно так, как вы хотели! Мы можем сделать это в методе LCS, используя один массив, но накладные расходы в этом случае заключаются в том, что вам придется вручную проверять каждую комбинацию, если это палиндром. См. Ниже решение для этого способа. Это было принято и на LC.

    public String longestPalindrome(String s) {
        int maxlen = 1;
        int len = s.length();
        String[] dp = new String[len];
        dp[0] = s.substring(0,1);
        for (int i = 1; i < len; i++) {
            dp[i] = dp[i-1];
            for (int j = 0; i - j >= maxlen; j++) {
                if (s.charAt(j) != s.charAt(i)) continue;
                if (isPal(s.substring(j, i + 1))) {
                    dp[i] = s.substring(j, i + 1);
                    maxlen = i - j;
                    break;
                }
            }
        }
        return dp[len-1];
    }
    
    public boolean isPal(String s) {
        for (int i = 0; i < s.length()/2; i++) {
            if (s.charAt(i) != s.charAt(s.length()-1-i)) return false;
        }
        return true;
    }
person berlin    schedule 30.10.2020
comment
@emma На самом деле я не очень хорошо понял ваше решение, поэтому я делюсь тем, которое закодировано мной, которое не удалось на данном тестовом примере на leetcode aacabdkacaa. здесь - это ссылка на мой код, который не прошел в приведенном выше тестовом примере. Правильный вывод должен быть aca, но мой код дает aaca, читающий первые четыре символа спереди и последние 4 с конца строки. Пожалуйста, помогите мне исправить мой код. - person NITESH SHARMA; 31.10.2020
comment
@NITESHSHARMA Я написал это решение, а не Эмма. ссылка не работает я получаю 404 не найдено, может вы могли бы попробовать еще раз? - person berlin; 31.10.2020