如何编写代码实现一个字符串的最长回文子串

这篇文章主要介绍“如何编写代码实现一个字符串的最长回文子串”，在日常操作中，相信很多人在如何编写代码实现一个字符串的最长回文子串问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”如何编写代码实现一个字符串的最长回文子串”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

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

到此，关于“如何编写代码实现一个字符串的最长回文子串”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！