20201124

5. 最长回文子串

image.png

  • 动态规划
  • 中心扩散
  • Manacher 算法

动态规划 回归方程：image.png

  1. //动态规划
  2. class Solution {
  3.     public String longestPalindrome(String s) {
  4.         int n = s.length();
  5.         boolean[][] dp = new boolean[n][n];
  6.         String ans = "";
  7.         for (int l = 0; l < n; ++l) {
  8.             for (int i = 0; i + l < n; ++i) {
  9.                 int j = i + l;
  10.                 if (l == 0) {
  11.                     dp[i][j] = true;
  12.                 } else if (l == 1) {
  13.                     dp[i][j] = (s.charAt(i) == s.charAt(j));
  14.                 } else {
  15.                     dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
  16.                 }
  17.                 if (dp[i][j] && l + 1 > ans.length()) {
  18.                     ans = s.substring(i, i + l + 1);
  19.                 }
  20.             }
  21.         }
  22.         return ans;
  23.     }
  24. }