题解 | #最长回文子串#

package com.hhdd.dp;

/**
 * 对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。
 * 题目链接：https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af?tpId=295&tqId=25269&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj%3Ftab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295
 *
 * @Author HuangLusong
 * @Date 2022/4/2 22:05
 */
public class 最长回文子串 {

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * <p>
     * 还是使用从点到面的思路
     * 如果将回文串字符展开成面一一对应，会发现其呈x型的特点
     * 也可以利用这个特点找回文子串，因为子串必然有此特点，只不过是蜷缩到这个面的局部，而不是整体
     *
     * @param A string字符串
     * @return int整型
     */
    public int getLongestPalindrome(String A) {
        // write code here

        int length = A.length();
        /**
         * 标记i，j位置的字符串是否相同，如果相同则标记为1
         */
        int[][] flags = new int[length][length];
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (A.charAt(i) == A.charAt(j)) {
                    flags[i][j] = 1;
                }
            }
        }
        /**
         * 接下来找左下方向的直线就可以
         */
        int res = 0;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                /**
                 * 为1说明有机会成为回文串 错误！
                 * 成为回文串必须是个正的x
                 */
                if (flags[i][j] == 1) {
                    int tempI = i;
                    int tempJ = j;
                    int tempLength = 0;
                    while (tempI < length && tempJ >= 0) {
                        if (flags[tempI][tempJ] == 1) {
                            tempLength++;

                            tempI++;
                            tempJ--;
                        } else {
                            break;
                        }
                    }
                    //通过头尾两点确定中点，中点必须符合i = j，否则将不是回文串
                    /**
                     * 先还原到上一个点
                     */
                    tempI--;
                    tempJ++;
                    if ((tempI + i) / 2 == (tempJ + j) / 2) {
                        if (tempLength > res) {
                            res = tempLength;
                        }
                    }
                }
            }
        }
        return res;

    }

    public static void main(String[] args) {

        最长回文子串 demo = new 最长回文子串();

        System.out.println(demo.getLongestPalindrome("acbdcbbbdbdaaccbcacdacdccababcddabddaaaaaaabdbabcdddaacabacbacbbdabdacddbbadaacbbdcbccacacdabcabacacbbbdcccacdcdcdcbcbabdcdacdddbbabcaccddddddabdacaabccdcabcbcbabacaaaccaccaddabbdadcdacdcdbaadbcabdcdcaaacbcadccbbddbaddcaddcaadcbbcbbdcbdadcddabdddcdbddbbdabaaddcaadd"));


    }


}