如何編寫代碼實現一個字符串的最長回文子串

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

/**
 * @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) {

        /**
         * 這個問題用的是從上而下的動態規劃求解方法，講求字符串A的最長回文子序列問題，
         * 轉換成三個子問題：求A.sutString(1,A.length)、求A.sutString(0,A.length-1)
         * 以及A.sutString(1,A.length-1)三種情況的解，并比較三種情況的解，得到最優解
         * 
         * 首先驗證參數合法性，在定義一個二維數組用于記錄已經求結果的子問題的解，主要的求解過程
         * 在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;

        /**
         * 參數不合法直接返回null
         */
        if(start<0 || end<0 || start>=solArr.length || end>=solArr.length || start > end)
            return null;
        else
        {
            /**
             * 如果當前子問題已經被求結果，直接返回在dp中記錄的結果
             */
            if(solArr[start][end]!=null)
            {
                return solArr[start][end];
            }
            else if (start == end)
            {
                /**
                 * 用于處理只有一個字符的子串的情況
                 */
                res = new Optimum(start,end,theStr);
            }
            else
            {
                /**
                 * 分別求解三種子問題的最優解
                 */
                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是相鄰的整數，如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);
                }

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

                res = finest;

            }
        }

        /**
         * 講此子問題的最優解記錄到數組中
         */
        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);
    }
}

到此，關于“如何編寫代碼實現一個字符串的最長回文子串”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！