题解 | #最长回文子串#

import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        //边界条件判断
        if (n < 2)
            return A.length();
        // 对于返回回文子串的问题，需要记录起始和结尾位置
        // start表示最长回文串开始的位置，end表示结束
        int start = 0,end = 0;
        //maxLen表示最长回文串的长度
        int maxLen = 1;

        // 从(i,i) 和 (i,i+1)开始扩展 找出以该点为起点的最长子串长度，从而确定start和end
        for(int i = 0;i < n; i++) {
            int len1 = getLen(A,i,i);
            int len2 = getLen(A,i,i+1);
            maxLen = Math.max(maxLen,Math.max(len1,len2));

            // 对于返回回文子串的问题
            if(maxLen > end - start + 1) {
                start = i - (maxLen - 1) / 2;
                end   = i + maxLen / 2; 
            }
        }

        //最长的回文子串长度
        return maxLen;
        //最长的回文子串
        // return A.substring(start,end+1); 
    }

    int getLen(String A,int i,int j){
        while(i >= 0 && j < A.length()) {
            if(A.charAt(i) != A.charAt(j)) {
                break;
            }
            i--;
            j++;
        }
        return j-i-1;
    }





//     public int getLongestPalindrome(String A, int n) {
//         //边界条件判断
//         if (n < 2)
//             return A.length();
//         //start表示最长回文串开始的位置，
//         //maxLen表示最长回文串的长度
//         int maxLen = 1;
//         boolean[][] dp = new boolean[n][n];
//         for (int right = 1; right < n; right++) {
//             for (int left = 0; left <= right; left++) {
//                 //如果两种字符不相同，肯定不能构成回文子串
//                 if (A.charAt(left) != A.charAt(right))
//                     continue;

//                 //下面是s.charAt(left)和s.charAt(right)两个
//                 //字符相同情况下的判断
//                 //如果只有一个字符，肯定是回文子串
//                 if (right == left) {
//                     dp[left][right] = true;
//                 } else if (right - left <= 2) {
//                     //类似于"aa"和"aba"，也是回文子串
//                     dp[left][right] = true;
//                 } else {
//                     //类似于"a******a"，要判断他是否是回文子串，只需要
//                     //判断"******"是否是回文子串即可
//                     dp[left][right] = dp[left + 1][right - 1];
//                 }
//                 //如果字符串从left到right是回文子串，只需要保存最长的即可
//                 if (dp[left][right] && right - left + 1 > maxLen) {
//                     maxLen = right - left + 1;
//                 }
//             }
//         }
//         //最长的回文子串
//         return maxLen;
//     }
}