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

這篇文章主要介紹“如何編寫代碼實現(xiàn)一個字符串的最長回文子串”，在日常操作中，相信很多人在如何編寫代碼實現(xiàn)一個字符串的最長回文子串問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”如何編寫代碼實現(xiàn)一個字符串的最長回文子串”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

/**
 * @author pxu
 * @create 2021/4/7-2:28 下午
 */
public class Nc017 {


    public static void main(String[] args) {

        String str = "abc1234321ab";

        Nc017 nc017 = new Nc017();

        int longestPalindrome = nc017.getLongestPalindrome(str, str.length());
        
        System.out.println(longestPalindrome);

    }


    public int getLongestPalindrome(String A, int n) {

        /**
         * 這個問題用的是從上而下的動態(tài)規(guī)劃求解方法，講求字符串A的最長回文子序列問題，
         * 轉換成三個子問題：求A.sutString(1,A.length)、求A.sutString(0,A.length-1)
         * 以及A.sutString(1,A.length-1)三種情況的解，并比較三種情況的解，得到最優(yōu)解
         * 
         * 首先驗證參數(shù)合法性，在定義一個二維數(shù)組用于記錄已經(jīng)求結果的子問題的解，主要的求解過程
         * 在helper方法中
         */

        switch (n)
        {
            case 0:
                return 0;
            case 1:
                return 1;
            default:
            {
                Optimum[][] dp = new Optimum[n][n];
                Optimum optimum = helper(A, dp, 0, n - 1);
                return optimum.len;
            }
        }

    }

    public Optimum helper(String theStr, Optimum[][] solArr, int start, int end)
    {
        /**
         * 此方法的最終返回結果
         */
        Optimum res = null;

        /**
         * 參數(shù)不合法直接返回null
         */
        if(start<0 || end<0 || start>=solArr.length || end>=solArr.length || start > end)
            return null;
        else
        {
            /**
             * 如果當前子問題已經(jīng)被求結果，直接返回在dp中記錄的結果
             */
            if(solArr[start][end]!=null)
            {
                return solArr[start][end];
            }
            else if (start == end)
            {
                /**
                 * 用于處理只有一個字符的子串的情況
                 */
                res = new Optimum(start,end,theStr);
            }
            else
            {
                /**
                 * 分別求解三種子問題的最優(yōu)解
                 */
                Optimum left = helper(theStr, solArr, start + 1, end);
                Optimum right = helper(theStr, solArr, start, end - 1);
                Optimum mid = helper(theStr, solArr, start + 1, end - 1);

                /**
                 * 如果start位置和end位置的字符相等，那么需要對A.sutString(1,A.length-1)類型問題
                 * 的解進一步處理
                 */
                if(theStr.charAt(start) == theStr.charAt(end))
                {
                    /**
                     * 如果start和end是相鄰的整數(shù)，如6和7，那么從上面的代碼可以知道此時mid一定是null，
                     * 但是此時的start位置和end位置的字符相等，那么mid解應該是一個長度為2的回文串。
                     * 
                     * 如果mid不是null，并且mid解的回文串的起止位置剛好和start和end相鄰，那么說明該解
                     * 可以被進一步延長，吧start和end位置的字符也包括進去。
                     */
                    
                    if(mid == null || (mid.start == start+1 && mid.end == end-1))
                        mid = new Optimum(start,end,theStr);
                }

                /**
                 * 比較并獲取最優(yōu)解
                 */
                Optimum finest = left;
                if (mid!=null && mid.len>finest.len)
                    finest = mid;
                if (right!=null && right.len>finest.len)
                    finest = right;

                res = finest;

            }
        }

        /**
         * 講此子問題的最優(yōu)解記錄到數(shù)組中
         */
        solArr[start][end] = res;

        /**
         * 返回解
         */
        return res;

    }


}

class Optimum {
    /**
     * 此類代表原始字符串的一個子串的最長回文子串
     * @param start 此回文串在原始字符串中的起始偏移量
     * @param end 此回文串在原始字符串中的終止偏移量
     * @param len 此回文串的長度
     * @param str 此回文串本身
     */

    int start = 0;
    int end = 0;
    int len = -1;
    String str = "";

    @Override
    public String toString() {
        return "Solution{" +
                "start=" + start +
                ", end=" + end +
                ", len=" + len +
                ", str='" + str + '\'' +
                '}';
    }

    public Optimum() {
    }
    
    public Optimum(int start, int end, String oriStr) {
        this.start = start;
        this.end = end;
        this.len = end-start+1;
        this.str = oriStr.substring(start,end+1);
    }
}

到此，關于“如何編寫代碼實現(xiàn)一個字符串的最長回文子串”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續(xù)學習更多相關知識，請繼續(xù)關注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>