解法1:暴力解法

直接判断每一个子串是不是回文子串,然后取其中最长的值返回

public class Palindrome {
    public int getLongestPalindrome(String A, int n) {
        int maxLen = 0;
        //暴力解法
        for(int i = 0; i < n; i++){
            for(int j = i+1; j <= n; j++){
                String now = A.substring(i,j);
                if(isPalindrome(now) && now.length() > maxLen){
                    maxLen = now.length();
                }
            }
        }
        return maxLen;
    }

    //判断子串是不是回文子串
    public boolean isPalindrome(String s){
        int l = s.length();
        for(int i = 0; i < l/2; i++){
            if(s.charAt(i) != s.charAt(l-i-1))
                return false;
        }
        return true;
    }
}

解法2:动态规划

动态规划算法中两个重要概念是边界以及状态转移方程;
dp[i][j]是一个bool类型的变量数组,如果dp[i][j]==true,那么他表示字符串str从str[i]到str[j]是回文串

  • 边界是:dp[i][i]=true,dp[i][i+1]=(str[i]==str[i+1]) ? true , false

状态转移方程:

  • dp[i][j]=true if( dp[i+1][j-1] && str[i]==str[j] )

  • dp[i][j]=false if( str[i]!=str[j] )

    public int getLongestPalindrome(String A, int n) {
          // write code here
          boolean[][] dp = new boolean[n][n];
          String ans = "";
          //l:字符串首尾字母长度差 (d = j-i)
          for (int l = 0; l < n; ++l){// 字符串起始位置 i
              for (int i = 0; i + l < n; ++i) {
                  int j = i + l;// 字符串结束位置 j
                  if (l == 0) {
                      dp[i][j] = true;
                  } else if (l == 1) {
                      dp[i][j] = (A.charAt(i) == A.charAt(j));
                  } else {
                      dp[i][j] = (A.charAt(i) == A.charAt(j) && dp[i + 1][j - 1]);
                  }
                  if (dp[i][j] && l + 1 > ans.length()) {
                      // 更新最大长度
                      ans = A.substring(i, i + l + 1);
                  }
              }
          }
          return ans.length();
      }

    解法3:中心扩散法

    https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-fa-he-dong-tai-gui-hua-by-reedfa/
    中心扩散法怎么去找回文串?
    从每一个位置出发,向两边扩散即可。遇到不是回文的时候结束。举个例子,str=acdbbdaa 我们需要寻找从第一个 b(位置为 33)出发最长回文串为多少。怎么寻找?
    首先往左寻找与当期位置相同的字符,直到遇到不相等为止。
    然后往右寻找与当期位置相同的字符,直到遇到不相等为止。
    最后左右双向扩散,直到左和右不相等。如下图所示:
    图片说明
    每个位置向两边扩散都会出现一个窗口大小(len);
    如果 len>maxLen(用来表示最长回文串的长度)。则更新 maxLen 的值。
    因为我们最后要返回的是具体子串,而不是长度,
    因此,还需要记录一下 maxLen 时的起始位置(maxStart),即此时还要 maxStart=len。
    时间复杂度:O(n^2),其中 n 是字符串的长度。长度为 1 和 2 的回文中心分别有 n 和 n−1 个,每个回文中心最多会向外扩展 O(n) 次。

    public class Palindrome {
      public int getLongestPalindrome(String A, int n) {
          if(n == 0)
              return 0;
          int maxLen = 1;
          //中心枚举到n-2位置
          for(int i = 0; i < n-1; i++){
              // 比较以i为中心扩散的回文子串 
              //&& 以i和i+1为中心扩散的回文子串 哪个大取哪个
              int len = centerSpread(A,i,i) > centerSpread(A,i,i+1)? centerSpread(A,i,i):centerSpread(A,i,i+1);
              maxLen = Math.max(maxLen,len);   
          }
          return maxLen;
      }
    
      //若left==right 则扩散中点为一个,此时的回文子串为奇数
      //若left!=right,则扩散的中点为 left和right,此时的回文子串为偶数
      public int centerSpread(String s, int left, int right){
          int len = s.length();
          int l = left;
          int r = right;
          while(l >= 0 && r <= len-1){
              //若相等则继续扩散
              if(s.charAt(l) == s.charAt(r)){
                  l--;
                  r++;
              }else{
                  break;
              }
          }
          //为什么还要减2  因为上面while循环终止了,此时s.charAt(l) != s.charAt(r)
          //所以此时的回文子串的左右边界其实是  l-1,  r-1
          return r-l+1-2;
      }
    }