一、题目内容

二、题解

解法1：

思路

动态规划
令dp[i][j]表示S[i]至S[j]所表示的子串是否是回文子串，是则为1，不是为0。

• 若S[i]=S[j]
  • 那么只要S[i+1]和S[j-1]是回文子串，S[i+1]至S[j-1]就是回文子串；
  • 如果S[i+1]至S[j-1]不是回文子串，则S[i]至S[j]一定不是回文子串。
• 若S[i]!=S[j]
  • 那S[i]至S[j]一定不是回文子串。

代码

public class Solution {
    public int getLongestPalindrome(String s, int n) {
        // write code here
        if (n < 2) {
            return s.length();
        }
        int maxLen = 1;
        boolean[][] dp = new boolean[n][n];
        for (int right = 1; right < n; right++) {
            for (int left = 0; left <= right; left++) {
                if (s.charAt(left) != s.charAt(right)) {
                    continue;
                }
                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;
    }
}