image.png

解题思路

动态规划

image.png

  1. public String longestPalindrome(String s) {
  2. int length = s.length();
  3. String res = "";
  4. boolean[][] dp = new boolean[length][length];
  5. for(int i=length-1;i>=0;i--){
  6. for(int j=i;j<length;j++){
  7. //计算dp
  8. dp[i][j]=s.charAt(i)==s.charAt(j)&&(j-i<3||dp[i+1][j-1]);
  9. //计算最大回文
  10. if(dp[i][j]&&j-i+1>res.length())
  11. res = s.substring(i, j+1);
  12. }
  13. }
  14. return res;
  15. }

中心扩展法

image.png

  1. public String longestPalindrome(String s) {
  2. if(s.equals(""))
  3. return "";
  4. int l = 0; //记录左边的索引
  5. int r = 0; //记录右边的索引
  6. int maxLength = 0;
  7. int n = s.length();
  8. for(int i =0;i<n;i++){
  9. //对于aba类的情况
  10. for(int step=0;step<Math.min(i+1,n-i);step++){ //step表示扩展的长度
  11. if(s.charAt(i-step)!=s.charAt(i+step))
  12. break; //不对称则退出
  13. if(2*step+1>maxLength){ //记录最大值
  14. maxLength = 2*step+1;
  15. l = i-step;
  16. r = i+step;
  17. }
  18. }
  19. //对于abba类问题
  20. if(i+1<n&&s.charAt(i)==s.charAt(i+1)){
  21. //注意下标
  22. for(int step=0;step<Math.min(i+1,n-i-1);step++){
  23. if(s.charAt(i-step)!=s.charAt(i+step+1))
  24. break;
  25. if(2*step+2>maxLength){ //长度值是不同的
  26. maxLength = 2*step+2;
  27. l = i-step;
  28. r = i+step+1;
  29. }
  30. }
  31. }
  32. }
  33. return s.substring(l,r+1); //返回最大的子串
  34. }