如何編寫代碼實現(xiàn)一個字符串的最長回文子序列

本篇內(nèi)容介紹了“如何編寫代碼實現(xiàn)一個字符串的最長回文子序列”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細閱讀，能夠?qū)W有所成！

import java.util.Arrays;

/**
 * @author pxu
 * @create 2021/4/7-5:57 下午
 */
public class Nc154 {
    

    public int longestPalindromeSubSeq (String s) {

        int n = s.length();
        /**
         * 在for循環(huán)運行過程中，dp[j]中的數(shù)據(jù)代表s從i到j(luò)的子串中的最長回文序列的長度
         * 在for運行結(jié)束后，dp[j]中的數(shù)據(jù)代表s從0到j(luò)的子串中的最長回文序列的長度，所
         * 以程序最后返回的結(jié)果就是dp[n-1]的值。
         */
        int[] dp = new int[n];

        /**
         * 填充為1的原因是，每一個字符都是一個長度為1的回文串
         */
        Arrays.fill(dp,1);

        for (int i = n-2;i>=0;i--) {

            /**
             * pre總是代表在字符串s從i+1到j(luò)-1的子串的最長的回文序列的長度，所以其初始值被設(shè)置為0
             */
            int pre=0;
            for (int j=i+1;j<n;j++) {
                /**
                 * 因為第i個字符可能會和第j個字符結(jié)合成回文對，導(dǎo)致原有dp[j]_old的值變?yōu)樵赿p[j-1]基礎(chǔ)上
                 * 增加2形成新的dp[j]_new，但是如果第i個字符也可以和第j+1個字符結(jié)合成回文對，這時候
                 * 對于第j+1個字符來說，第j個字符是沒有和第i個字符結(jié)合的（因為第i個字符，只能和后面的一個字符結(jié)合）
                 * ，所以dp[j+1]的新值應(yīng)該是dp[j]的舊值的基礎(chǔ)上增加2得到。所以每次進入循環(huán)的時候需要把dp[j]的值
                 * 記錄在temp變量中，在本次循環(huán)結(jié)束之前，將值傳遞給pre，以便于在下一次循環(huán)中如果下一個字符也可以
                 * 和第i個字符結(jié)合時，更新dp中的值
                 */
                int temp = dp[j];
                if (s.charAt(i) == s.charAt(j)) {
                    dp[j] = pre + 2;
                }else {
                    dp[j] = Math.max(dp[j],dp[j-1]);
                }

                pre = temp;
            }
        }
        return dp[n-1];

    }

}

“如何編寫代碼實現(xiàn)一個字符串的最長回文子序列”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！